<!DOCTYPE html>
<html lang="zh-CN">
    <head>
        <meta charset="utf-8">
        <meta name="viewport" content="width=device-width, initial-scale=1">
        <meta name="robots" content="noodp" />
        <title>徒手写的AVL竟然比STL中的红黑树效率更高？✨ - L_B__</title><meta name="referrer" content="no-referrer">
<meta name="description" content="徒手写的AVL竟然比STL中的红黑树效率更高？✨"><meta property="og:title" content="徒手写的AVL竟然比STL中的红黑树效率更高？✨" />
<meta property="og:description" content="徒手写的AVL竟然比STL中的红黑树效率更高？✨" />
<meta property="og:type" content="article" />
<meta property="og:url" content="https://acking-you.github.io/posts/%E5%BE%92%E6%89%8B%E5%86%99%E7%9A%84avl%E7%AB%9F%E7%84%B6%E6%AF%94stl%E4%B8%AD%E7%9A%84%E7%BA%A2%E9%BB%91%E6%A0%91%E6%95%88%E7%8E%87%E6%9B%B4%E9%AB%98/" /><meta property="og:image" content="https://acking-you.github.io/logo.png"/><meta property="article:section" content="posts" />
<meta property="article:published_time" content="2022-02-16T00:00:00+00:00" />
<meta property="article:modified_time" content="2022-02-16T00:00:00+00:00" />

<meta name="twitter:card" content="summary_large_image"/>
<meta name="twitter:image" content="https://acking-you.github.io/logo.png"/>

<meta name="twitter:title" content="徒手写的AVL竟然比STL中的红黑树效率更高？✨"/>
<meta name="twitter:description" content="徒手写的AVL竟然比STL中的红黑树效率更高？✨"/>
<meta name="application-name" content="FeelIt">
<meta name="apple-mobile-web-app-title" content="FeelIt"><meta name="theme-color" content="#ffffff"><meta name="msapplication-TileColor" content="#da532c"><link rel="canonical" href="https://acking-you.github.io/posts/%E5%BE%92%E6%89%8B%E5%86%99%E7%9A%84avl%E7%AB%9F%E7%84%B6%E6%AF%94stl%E4%B8%AD%E7%9A%84%E7%BA%A2%E9%BB%91%E6%A0%91%E6%95%88%E7%8E%87%E6%9B%B4%E9%AB%98/" /><link rel="prev" href="https://acking-you.github.io/posts/%E6%96%B0%E6%89%8B%E7%94%A8c&#43;&#43;%E5%86%99%E4%BA%86%E4%B8%AA%E6%B3%9B%E5%9E%8B%E5%A0%86%E6%95%88%E7%8E%87%E7%AB%9F%E6%AF%94stl%E7%9A%84%E6%9B%B4%E5%BF%AB/" /><link rel="next" href="https://acking-you.github.io/posts/java%E8%BF%9E%E6%8E%A5%E6%95%B0%E6%8D%AE%E5%BA%93/" /><link rel="stylesheet" href="/css/page.min.css"><link rel="stylesheet" href="/css/home.min.css"><script type="application/ld+json">
    {
        "@context": "http://schema.org",
        "@type": "BlogPosting",
        "headline": "徒手写的AVL竟然比STL中的红黑树效率更高？✨",
        "inLanguage": "zh-CN",
        "mainEntityOfPage": {
            "@type": "WebPage",
            "@id": "https:\/\/acking-you.github.io\/posts\/%E5%BE%92%E6%89%8B%E5%86%99%E7%9A%84avl%E7%AB%9F%E7%84%B6%E6%AF%94stl%E4%B8%AD%E7%9A%84%E7%BA%A2%E9%BB%91%E6%A0%91%E6%95%88%E7%8E%87%E6%9B%B4%E9%AB%98\/"
        },"genre": "posts","keywords": "徒手写的AVL竟然比STL中的红黑树效率更高？✨","wordcount":  6638 ,
        "url": "https:\/\/acking-you.github.io\/posts\/%E5%BE%92%E6%89%8B%E5%86%99%E7%9A%84avl%E7%AB%9F%E7%84%B6%E6%AF%94stl%E4%B8%AD%E7%9A%84%E7%BA%A2%E9%BB%91%E6%A0%91%E6%95%88%E7%8E%87%E6%9B%B4%E9%AB%98\/","datePublished": "2022-02-16T00:00:00+00:00","dateModified": "2022-02-16T00:00:00+00:00","publisher": {
            "@type": "Organization",
            "name": "作者"},"author": {
                "@type": "Person",
                "name": "作者"
            },"description": "徒手写的AVL竟然比STL中的红黑树效率更高？✨"
    }
    </script></head><body data-header-desktop="auto" data-header-mobile="auto"><script>(window.localStorage && localStorage.getItem('theme') ? localStorage.getItem('theme') === 'dark' : ('auto' === 'auto' ? window.matchMedia('(prefers-color-scheme: dark)').matches : 'auto' === 'dark')) && document.body.setAttribute('theme', 'dark');</script>

        <div id="mask"></div><div class="wrapper"><header class="desktop" id="header-desktop">
    <div class="header-wrapper">
        <div class="header-title">
            <a href="/" title="L_B__">L_B__</a>
        </div>
        <div class="menu">
            <div class="menu-inner"><a class="menu-item" href="/posts/"> 文章 </a><a class="menu-item" href="/tags/"> 标签 </a><a class="menu-item" href="/categories/"> 分类 </a><span class="menu-item delimiter"></span><span class="menu-item search" id="search-desktop">
                        <input type="text" placeholder="搜索文章标题或内容..." id="search-input-desktop">
                        <a href="#" class="search-button search-toggle" id="search-toggle-desktop" title="搜索">
                            <i class="fas fa-search fa-fw"></i>
                        </a>
                        <a href="#" class="search-button search-clear" id="search-clear-desktop" title="清空">
                            <i class="fas fa-times-circle fa-fw"></i>
                        </a>
                        <span class="search-button search-loading" id="search-loading-desktop">
                            <i class="fas fa-spinner fa-fw fa-spin"></i>
                        </span>
                    </span><a href="javascript:void(0);" class="menu-item theme-switch" title="切换主题">
                    <i class="fas fa-adjust fa-fw"></i>
                </a>
            </div>
        </div>
    </div>
</header><header class="mobile" id="header-mobile">
    <div class="header-container">
        <div class="header-wrapper">
            <div class="header-title">
                <a href="/" title="L_B__">L_B__</a>
            </div>
            <div class="menu-toggle" id="menu-toggle-mobile">
                <span></span><span></span><span></span>
            </div>
        </div>
        <div class="menu" id="menu-mobile"><div class="search-wrapper">
                    <div class="search mobile" id="search-mobile">
                        <input type="text" placeholder="搜索文章标题或内容..." id="search-input-mobile">
                        <a href="#" class="search-button search-toggle" id="search-toggle-mobile" title="搜索">
                            <i class="fas fa-search fa-fw"></i>
                        </a>
                        <a href="#" class="search-button search-clear" id="search-clear-mobile" title="清空">
                            <i class="fas fa-times-circle fa-fw"></i>
                        </a>
                        <span class="search-button search-loading" id="search-loading-mobile">
                            <i class="fas fa-spinner fa-fw fa-spin"></i>
                        </span>
                    </div>
                    <a href="#" class="search-cancel" id="search-cancel-mobile">
                        取消
                    </a>
                </div><a class="menu-item" href="/posts/" title="">文章</a><a class="menu-item" href="/tags/" title="">标签</a><a class="menu-item" href="/categories/" title="">分类</a><div class="menu-item"><a href="javascript:void(0);" class="theme-switch" title="切换主题">
                    <i class="fas fa-adjust fa-fw"></i>
                </a>
            </div></div>
    </div>
</header><div class="search-dropdown desktop">
    <div id="search-dropdown-desktop"></div>
</div>
<div class="search-dropdown mobile">
    <div id="search-dropdown-mobile"></div>
</div><main class="main">
                <div class="container"><div class="toc" id="toc-auto">
            <h2 class="toc-title">目录</h2>
            <div class="toc-content" id="toc-content-auto"></div>
        </div><article class="page single" data-toc="disable"><div class="featured-image"><img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/img_convert/8db816efd6abe83538c4d47108d9c840.png#pic_center"
        data-srcset="https://img-blog.csdnimg.cn/img_convert/8db816efd6abe83538c4d47108d9c840.png#pic_center, https://img-blog.csdnimg.cn/img_convert/8db816efd6abe83538c4d47108d9c840.png#pic_center 1.5x, https://img-blog.csdnimg.cn/img_convert/8db816efd6abe83538c4d47108d9c840.png#pic_center 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/img_convert/8db816efd6abe83538c4d47108d9c840.png#pic_center"
        title="徒手写的AVL竟然比STL中的红黑树效率更高？✨" /></div><div class="single-card" data-image="true"><h2 class="single-title animated flipInX">徒手写的AVL竟然比STL中的红黑树效率更高？✨</h2><div class="post-meta">
                <div class="post-meta-line"><span class="post-author"><a href="/" title="Author" rel=" author" class="author"><i class="fas fa-user-circle fa-fw"></i>作者</a></span>&nbsp;<span class="post-category">出版于  <a href="/categories/%E6%89%8B%E5%86%99%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/"><i class="far fa-folder fa-fw"></i>手写数据结构</a></span></div>
                <div class="post-meta-line"><span><i class="far fa-calendar-alt fa-fw"></i>&nbsp;<time datetime="2022-02-16">2022-02-16</time></span>&nbsp;<span><i class="fas fa-pencil-alt fa-fw"></i>&nbsp;约 6638 字</span>&nbsp;
                    <span><i class="far fa-clock fa-fw"></i>&nbsp;预计阅读 14 分钟</span>&nbsp;</div>
            </div>
            
            <hr><div class="details toc" id="toc-static"  data-kept="">
                    <div class="details-summary toc-title">
                        <span>目录</span>
                        <span><i class="details-icon fas fa-angle-right"></i></span>
                    </div>
                    <div class="details-content toc-content" id="toc-content-static"><nav id="TableOfContents">
  <ul>
    <li><a href="#avl树简介">AVL树简介</a></li>
    <li><a href="#avl树的相关概念">AVL树的相关概念</a></li>
    <li><a href="#avl树的实现详解">AVL树的实现详解</a>
      <ul>
        <li><a href="#1-结点结构">1. 结点结构</a></li>
        <li><a href="#2-avl树的抽象数据结构adt">2. AVL树的抽象数据结构（ADT）</a></li>
        <li><a href="#3-avl树高度相关操作">3. AVL树高度相关操作</a></li>
        <li><a href="#4-得到子树中最大最小结点">4. 得到子树中最大/最小结点</a></li>
        <li><a href="#5-得到结点的前驱和后继">5. 得到结点的前驱和后继</a></li>
        <li><a href="#6-avl树失衡的调整">6. AVL树失衡的调整</a></li>
        <li><a href="#7-插入新结点">7. 插入新结点</a></li>
        <li><a href="#8-删除结点">8. 删除结点</a></li>
        <li><a href="#9-查找元素">9. 查找元素</a></li>
        <li><a href="#10-遍历二叉树">10. 遍历二叉树</a></li>
        <li><a href="#11-avl树的销毁">11. AVL树的销毁</a></li>
        <li><a href="#12-迭代器的设计">12. 迭代器的设计</a></li>
      </ul>
    </li>
    <li><a href="#完整代码">完整代码</a>
      <ul>
        <li><a href="#avltreeh">AVLTree.h</a></li>
        <li><a href="#avltreecpp">AVLTree.cpp</a></li>
      </ul>
    </li>
    <li><a href="#测试">测试</a>
      <ul>
        <li><a href="#测试代码">测试代码</a></li>
        <li><a href="#测试总结">测试总结</a></li>
      </ul>
    </li>
    <li><a href="#解题测试">解题测试</a></li>
  </ul>
</nav></div>
                </div><div class="content" id="content"><h2 id="avl树简介">AVL树简介</h2>
<p>AVL树的名字来源于它的发明作者G.M. Adelson-Velsky 和 E.M. Landis。AVL树是最先发明的自平衡二叉查找树（Self-Balancing Binary Search Tree,简称平衡二叉树）。</p>
<p>一棵AVL树有如下必要条件：</p>
<ol>
<li>条件一：它必须是二叉查找树。</li>
<li>条件二：每个节点的左子树和右子树的高度差至多为1。</li>
</ol>
<p><img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/c9d5b723b2624bd2848fdc2d470dac49.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        data-srcset="https://img-blog.csdnimg.cn/c9d5b723b2624bd2848fdc2d470dac49.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16, https://img-blog.csdnimg.cn/c9d5b723b2624bd2848fdc2d470dac49.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 1.5x, https://img-blog.csdnimg.cn/c9d5b723b2624bd2848fdc2d470dac49.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/c9d5b723b2624bd2848fdc2d470dac49.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        title="https://img-blog.csdnimg.cn/c9d5b723b2624bd2848fdc2d470dac49.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16" /></p>
<p>图一中左边二叉树的节点45的左孩子46比45大，不满足二叉搜索树的条件，因此它也不是一棵平衡二叉树。
右边二叉树满足二叉搜索树的条件，同时它满足条件二，因此它是一棵平衡二叉树。
<img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/d6b0bee18f854b938c59637dfb1f22a0.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        data-srcset="https://img-blog.csdnimg.cn/d6b0bee18f854b938c59637dfb1f22a0.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16, https://img-blog.csdnimg.cn/d6b0bee18f854b938c59637dfb1f22a0.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 1.5x, https://img-blog.csdnimg.cn/d6b0bee18f854b938c59637dfb1f22a0.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/d6b0bee18f854b938c59637dfb1f22a0.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        title="https://img-blog.csdnimg.cn/d6b0bee18f854b938c59637dfb1f22a0.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16" />
左边二叉树的节点45左子树高度2，右子树高度0，左右子树高度差为2-0=2，不满足条件二；右边二叉树的节点均满足左右子树高度差至多为1，同时它满足二叉搜索树的要求，因此它是一棵平衡二叉树。</p>
<p>AVL树的查找、插入、删除操作在平均和最坏的情况下都是O（logn），这得益于它时刻维护着二叉树的平衡。但由于每次插入都需要不断的调整和维护，所以，实际上如果插入操作次数太多则同样会陷入超时的死局，<strong>最具优势的操作在于查找，因为它的底层设计使得它无论插入多少个元素，这颗二叉树总是严格平衡的，所以AVL树适用于插入操作不是很频繁，但查找操作极度频繁的情况，如果需要在插入和查找操作找一个均衡点，那么就只能选择红黑树了。</strong></p>
<h2 id="avl树的相关概念">AVL树的相关概念</h2>
<ol>
<li>
<p><strong>平衡因子</strong>：将二叉树上节点的左子树高度减去右子树高度的值称为该节点的平衡因子BF(Balance Factor)。 
在图二右边的AVL树上：
节点50的左子树高度为3，右子树高度为2，BF= 3-2 = 1；
节点45的左子树高度为2，右子树高度为1，BF= 2-1 = 1；
节点46的左子树高度为0，右子树高度为0，BF= 0-0 = 0；
节点65的左子树高度为0，右子树高度为1，BF= 0-1 = -1；
对于平衡二叉树，BF的取值范围为[-1,1]。如果发现某个节点的BF值不在此范围，则需要对树进行调整。</p>
</li>
<li>
<p><strong>最小不平衡树</strong>：距离插入节点最近的，且平衡因子的绝对值大于1的节点为根的子树。
<img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/f7fc3c57360043c0b77928baafb23186.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        data-srcset="https://img-blog.csdnimg.cn/f7fc3c57360043c0b77928baafb23186.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16, https://img-blog.csdnimg.cn/f7fc3c57360043c0b77928baafb23186.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 1.5x, https://img-blog.csdnimg.cn/f7fc3c57360043c0b77928baafb23186.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/f7fc3c57360043c0b77928baafb23186.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        title="https://img-blog.csdnimg.cn/f7fc3c57360043c0b77928baafb23186.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16" />
在图三中，左边二叉树的节点45的BF = 1，插入节点43后，节点45的BF = 2。节点45是距离插入点43最近的BF不在[-1,1]范围内的节点，因此以节点45为根的子树为最小不平衡子树。(这正好对应了递归的后序返回操作</p>
</li>
<li>
<p><strong>中序的前驱和后继</strong>：顾名思义，就是中序遍历下的前一个结点和后一个结点，由于时二叉搜索树，所以中序遍历的前一个结点对应比这个结点小的最大结点，而后一个结点对应比这个结点大的最小结点。<strong>(这个可以看后面代码再进行理解)这个概念在进行删除结点的操作时很有用，因为删除结点后需要同时保证仍然为二叉搜索树。</strong>
关于对前驱和后继的一些寻找方法，请看我的另一篇博客：<a href="https://blog.csdn.net/m0_50945504/article/details/120712546" target="_blank" rel="noopener noreffer">面试题 04.06. 后继者</a></p>
</li>
</ol>
<h2 id="avl树的实现详解">AVL树的实现详解</h2>
<blockquote>
<p>总体思维导图实现。</p>
</blockquote>
<p><img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/f04d2e81d923490f838fcda55071948f.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        data-srcset="https://img-blog.csdnimg.cn/f04d2e81d923490f838fcda55071948f.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16, https://img-blog.csdnimg.cn/f04d2e81d923490f838fcda55071948f.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 1.5x, https://img-blog.csdnimg.cn/f04d2e81d923490f838fcda55071948f.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/f04d2e81d923490f838fcda55071948f.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        title="https://img-blog.csdnimg.cn/f04d2e81d923490f838fcda55071948f.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16" /></p>
<h3 id="1-结点结构">1. 结点结构</h3>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="k">struct</span> <span class="nc">node</span> <span class="p">{</span>
    <span class="kt">int</span> <span class="n">val</span><span class="p">;</span>
    <span class="kt">int</span> <span class="n">depth</span><span class="p">;</span>
    <span class="n">node</span> <span class="o">*</span><span class="n">lchild</span><span class="p">;</span>
    <span class="n">node</span> <span class="o">*</span><span class="n">rchild</span><span class="p">;</span>

    <span class="n">node</span><span class="p">()</span> <span class="o">:</span> <span class="n">val</span><span class="p">(</span><span class="mi">0</span><span class="p">),</span> <span class="n">lchild</span><span class="p">(</span><span class="k">nullptr</span><span class="p">),</span> <span class="n">rchild</span><span class="p">(</span><span class="k">nullptr</span><span class="p">)</span> <span class="p">{}</span>

    <span class="n">node</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">)</span> <span class="o">:</span> <span class="n">val</span><span class="p">(</span><span class="n">x</span><span class="p">),</span> <span class="n">lchild</span><span class="p">(</span><span class="k">nullptr</span><span class="p">),</span> <span class="n">rchild</span><span class="p">(</span><span class="k">nullptr</span><span class="p">)</span> <span class="p">{}</span>
<span class="p">};</span>
</code></pre></div><ol>
<li>val，结点的值。</li>
<li>depth，该结点的高度(它的左右子树中最高的高度+1)。</li>
<li>lchild，左孩子。</li>
<li>rchild，右孩子。</li>
</ol>
<h3 id="2-avl树的抽象数据结构adt">2. AVL树的抽象数据结构（ADT）</h3>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="k">class</span> <span class="nc">AVLTree</span> <span class="p">{</span>
    <span class="cm">/*date part*/</span>
    <span class="n">node</span> <span class="o">*</span><span class="n">head</span><span class="p">;</span>
    <span class="kt">int</span> <span class="n">length</span><span class="p">;</span>
<span class="k">public</span><span class="o">:</span>
    <span class="cm">/*construct and destruct part*/</span>
    <span class="n">AVLTree</span><span class="p">()</span> <span class="o">:</span> <span class="n">head</span><span class="p">(</span><span class="k">nullptr</span><span class="p">),</span> <span class="n">length</span><span class="p">(</span><span class="mi">0</span><span class="p">)</span> <span class="p">{}</span>

    <span class="n">AVLTree</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">)</span> <span class="o">:</span> <span class="n">head</span><span class="p">(</span><span class="k">new</span> <span class="n">node</span><span class="p">(</span><span class="n">x</span><span class="p">)),</span> <span class="n">length</span><span class="p">(</span><span class="mi">1</span><span class="p">)</span> <span class="p">{}</span>

    <span class="o">~</span><span class="n">AVLTree</span><span class="p">()</span> <span class="p">{</span>
        <span class="n">destroy</span><span class="p">(</span><span class="n">head</span><span class="p">);</span>
    <span class="p">}</span>

<span class="k">public</span><span class="o">:</span>
    <span class="cm">/*iterator part*/</span>
    <span class="k">class</span> <span class="nc">iterator</span> <span class="p">{</span><span class="c1">//封装迭代器：内部类--只能调用外部类的静态函数
</span><span class="c1"></span>        <span class="n">node</span> <span class="o">*</span><span class="n">head</span><span class="p">;</span>
        <span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">;</span>
    <span class="k">public</span><span class="o">:</span>
        <span class="n">iterator</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">head</span><span class="p">,</span> <span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">)</span> <span class="o">:</span> <span class="n">head</span><span class="p">(</span><span class="n">head</span><span class="p">),</span> <span class="n">root</span><span class="p">(</span><span class="n">root</span><span class="p">)</span> <span class="p">{}</span>

        <span class="n">iterator</span> <span class="o">&amp;</span><span class="k">operator</span><span class="o">++</span><span class="p">();</span>

        <span class="kt">bool</span> <span class="k">operator</span><span class="o">==</span><span class="p">(</span><span class="k">const</span> <span class="n">iterator</span> <span class="o">&amp;</span><span class="n">x</span><span class="p">);</span>

        <span class="kt">bool</span> <span class="k">operator</span><span class="o">!=</span><span class="p">(</span><span class="k">const</span> <span class="n">iterator</span> <span class="o">&amp;</span><span class="n">x</span><span class="p">);</span>

        <span class="n">iterator</span> <span class="k">operator</span><span class="o">++</span><span class="p">(</span><span class="kt">int</span><span class="p">);</span>

        <span class="n">iterator</span> <span class="o">&amp;</span><span class="k">operator</span><span class="o">--</span><span class="p">();</span>

        <span class="n">iterator</span> <span class="k">operator</span><span class="o">--</span><span class="p">(</span><span class="kt">int</span><span class="p">);</span>

        <span class="kt">int</span> <span class="k">operator</span><span class="o">*</span><span class="p">();</span>
    <span class="p">};</span>

<span class="k">private</span><span class="o">:</span>
    <span class="cm">/*static member function*/</span>
    <span class="cm">/*Rotate Part*/</span>
    <span class="k">static</span> <span class="n">node</span> <span class="o">*</span><span class="n">rotateRight</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">);</span>

    <span class="k">static</span> <span class="n">node</span> <span class="o">*</span><span class="nf">rotateLeft</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">);</span>

    <span class="k">static</span> <span class="n">node</span> <span class="o">*</span><span class="nf">rotateLeftRight</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">);</span>

    <span class="k">static</span> <span class="n">node</span> <span class="o">*</span><span class="nf">rotateRightLeft</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">);</span>

    <span class="cm">/*Destruct*/</span>
    <span class="k">static</span> <span class="kt">void</span> <span class="nf">destroy</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">);</span>

    <span class="cm">/*Getter*/</span>
    <span class="k">static</span> <span class="n">node</span> <span class="o">*</span><span class="nf">getNext</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">,</span> <span class="n">node</span> <span class="o">*</span><span class="n">p</span><span class="p">);</span>

    <span class="k">static</span> <span class="n">node</span> <span class="o">*</span><span class="nf">getPre</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">,</span> <span class="n">node</span> <span class="o">*</span><span class="n">p</span><span class="p">);</span>

    <span class="k">static</span> <span class="n">node</span> <span class="o">*</span><span class="nf">getMinNode</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">);</span>

    <span class="k">static</span> <span class="n">node</span> <span class="o">*</span><span class="nf">getMaxNode</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">);</span>

    <span class="k">static</span> <span class="kt">int</span> <span class="nf">get_depth</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">);</span>

    <span class="k">static</span> <span class="kt">void</span> <span class="nf">update_depth</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">);</span>

    <span class="cm">/*Insert&amp;Remove*/</span>
    <span class="k">static</span> <span class="n">node</span> <span class="o">*</span><span class="nf">Insert</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">,</span> <span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">,</span> <span class="kt">int</span> <span class="o">&amp;</span><span class="n">size</span><span class="p">);</span>

    <span class="k">static</span> <span class="n">node</span> <span class="o">*</span><span class="nf">remove</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">,</span> <span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">,</span> <span class="kt">int</span> <span class="o">&amp;</span><span class="n">size</span><span class="p">);</span>

    <span class="cm">/*print_order*/</span>
    <span class="k">static</span> <span class="kt">void</span> <span class="nf">inorder</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">);</span>

<span class="k">public</span><span class="o">:</span>
    <span class="cm">/*public interface*/</span>
    <span class="cm">/*clear&amp;empty*/</span>
    <span class="kt">void</span> <span class="n">clear</span><span class="p">();</span>

    <span class="kt">bool</span> <span class="nf">isEmpty</span><span class="p">();</span>

    <span class="cm">/*find*/</span>
    <span class="kt">bool</span> <span class="nf">find</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">);</span>

    <span class="cm">/*insert&amp;remove*/</span>
    <span class="kt">void</span> <span class="nf">insert</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">);</span>

    <span class="kt">void</span> <span class="nf">remove</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">);</span>

    <span class="cm">/*size*/</span>
    <span class="kt">int</span> <span class="nf">size</span><span class="p">();</span>

    <span class="cm">/*begin&amp;end*/</span>
    <span class="n">iterator</span> <span class="nf">begin</span><span class="p">();</span>

    <span class="n">iterator</span> <span class="nf">end</span><span class="p">();</span>

    <span class="cm">/*print*/</span>
    <span class="kt">void</span> <span class="nf">inorder_print</span><span class="p">();</span>
<span class="p">};</span>
</code></pre></div><h3 id="3-avl树高度相关操作">3. AVL树高度相关操作</h3>
<p><strong>得到高度</strong></p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="k">static</span> <span class="kt">int</span> <span class="nf">get_depth</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">)</span> <span class="p">{</span><span class="c1">//得到深度
</span><span class="c1"></span>    <span class="k">if</span> <span class="p">(</span><span class="n">root</span> <span class="o">==</span> <span class="k">nullptr</span><span class="p">)</span>
        <span class="k">return</span> <span class="mi">0</span><span class="p">;</span>
    <span class="k">return</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">depth</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div><p><strong>更新高度</strong></p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="k">static</span> <span class="kt">void</span> <span class="nf">update_depth</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">)</span> <span class="p">{</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">root</span> <span class="o">==</span> <span class="k">nullptr</span><span class="p">)</span>
        <span class="k">return</span><span class="p">;</span>
    <span class="n">root</span><span class="o">-&gt;</span><span class="n">depth</span> <span class="o">=</span> <span class="n">std</span><span class="o">::</span><span class="n">max</span><span class="p">(</span><span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">),</span> <span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">))</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div><h3 id="4-得到子树中最大最小结点">4. 得到子树中最大/最小结点</h3>
<p>原理：根据二叉搜索树中结点的左子树一定小于该结点，右子树一定大于该结点。</p>
<p><strong>得到最大</strong>：直接遍历得出该结点的最右结点。</p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp">    <span class="k">static</span> <span class="n">node</span><span class="o">*</span> <span class="nf">getMaxNode</span><span class="p">(</span><span class="n">node</span><span class="o">*</span> <span class="n">root</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">root</span> <span class="o">==</span> <span class="k">nullptr</span><span class="p">)</span>
            <span class="k">return</span> <span class="k">nullptr</span><span class="p">;</span>
        <span class="k">while</span> <span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span> <span class="o">!=</span> <span class="k">nullptr</span><span class="p">)</span>
            <span class="n">root</span> <span class="o">=</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">;</span>
        <span class="k">return</span> <span class="n">root</span><span class="p">;</span>
    <span class="p">}</span>
</code></pre></div><p><strong>得到最小</strong>：直接遍历得出该结点的最左结点。</p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp">    <span class="k">static</span> <span class="n">node</span><span class="o">*</span> <span class="nf">getMinNode</span><span class="p">(</span><span class="n">node</span><span class="o">*</span> <span class="n">root</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">root</span> <span class="o">==</span> <span class="k">nullptr</span><span class="p">)</span>
            <span class="k">return</span> <span class="k">nullptr</span><span class="p">;</span>
        <span class="k">while</span> <span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span> <span class="o">!=</span> <span class="k">nullptr</span><span class="p">)</span>
            <span class="n">root</span> <span class="o">=</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">;</span>
        <span class="k">return</span> <span class="n">root</span><span class="p">;</span>
    <span class="p">}</span>
</code></pre></div><h3 id="5-得到结点的前驱和后继">5. 得到结点的前驱和后继</h3>
<p>注意：二叉搜索树的前驱后继一般指的是它中序遍历的前一个和后一个结点，也就是从小到大排的前一个和后一个结点。</p>
<p>具体可以看我之前的博客&ndash;<a href="https://blog.csdn.net/m0_50945504/article/details/120712546" target="_blank" rel="noopener noreffer">后继者</a></p>
<hr>
<p><strong>后继结点求解</strong>：如果有右子树，就是右子树的最小结点，如果没有，则是距离该节点最近的处于该节点右边的父节点。</p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="k">static</span> <span class="n">node</span><span class="o">*</span> <span class="nf">getNext</span><span class="p">(</span><span class="n">node</span><span class="o">*</span> <span class="n">root</span><span class="p">,</span> <span class="n">node</span><span class="o">*</span> <span class="n">p</span><span class="p">)</span> <span class="p">{</span> <span class="c1">//得到p节点的后继结点
</span><span class="c1"></span>    <span class="k">if</span> <span class="p">(</span><span class="n">root</span> <span class="o">==</span> <span class="k">nullptr</span> <span class="o">||</span> <span class="n">p</span> <span class="o">==</span> <span class="k">nullptr</span><span class="p">)</span> <span class="k">return</span> <span class="k">nullptr</span><span class="p">;</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">p</span><span class="o">-&gt;</span><span class="n">val</span> <span class="o">&gt;=</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">return</span> <span class="n">getNext</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">,</span> <span class="n">p</span><span class="p">);</span>
    <span class="p">}</span> <span class="k">else</span> <span class="p">{</span>
        <span class="n">node</span><span class="o">*</span> <span class="n">left</span> <span class="o">=</span> <span class="n">getNext</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">,</span> <span class="n">p</span><span class="p">);</span>
        <span class="k">return</span> <span class="n">left</span> <span class="o">?</span> <span class="nl">left</span> <span class="p">:</span> <span class="n">root</span><span class="p">;</span>
    <span class="p">}</span>
<span class="p">}</span>
</code></pre></div><p><strong>前驱结点求解</strong>：如果有左子树，就是左子树的最大结点，如果没有，则是距离该节点最近的处于该节点左边的父节点。</p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="k">static</span> <span class="n">node</span><span class="o">*</span> <span class="nf">getPre</span><span class="p">(</span><span class="n">node</span><span class="o">*</span> <span class="n">root</span><span class="p">,</span> <span class="n">node</span><span class="o">*</span> <span class="n">p</span><span class="p">)</span> <span class="p">{</span> <span class="c1">//得到p节点的前驱结点
</span><span class="c1"></span>    <span class="k">if</span> <span class="p">(</span><span class="n">root</span> <span class="o">==</span> <span class="k">nullptr</span> <span class="o">||</span> <span class="n">p</span> <span class="o">==</span> <span class="k">nullptr</span><span class="p">)</span><span class="k">return</span> <span class="k">nullptr</span><span class="p">;</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">p</span><span class="o">-&gt;</span><span class="n">val</span> <span class="o">&lt;=</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">return</span> <span class="n">getPre</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">,</span> <span class="n">p</span><span class="p">);</span>
    <span class="p">}</span> <span class="k">else</span> <span class="p">{</span>
        <span class="n">node</span><span class="o">*</span> <span class="n">right</span> <span class="o">=</span> <span class="n">getPre</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">,</span> <span class="n">p</span><span class="p">);</span>
        <span class="k">return</span> <span class="n">right</span> <span class="o">?</span> <span class="nl">right</span> <span class="p">:</span> <span class="n">root</span><span class="p">;</span>
    <span class="p">}</span>
<span class="p">}</span>
</code></pre></div><h3 id="6-avl树失衡的调整">6. AVL树失衡的调整</h3>
<p>节点的插入或删除都有可能导致AVL树失去平衡，因此，失衡调整是插入与删除操作的基础。
AVL树的失衡调整可以分为四种情况，我们逐一分析。
假设我们要为数组a[]={4，5，6，3，2，8，7，0，1}构建一棵AVL树。
<strong>情况一：左旋</strong>
首先插入{4，5，6}，在插入元素6后出现不平衡的情况：
<img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/5379467202d944c99c91b1a7744c6c50.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        data-srcset="https://img-blog.csdnimg.cn/5379467202d944c99c91b1a7744c6c50.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16, https://img-blog.csdnimg.cn/5379467202d944c99c91b1a7744c6c50.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 1.5x, https://img-blog.csdnimg.cn/5379467202d944c99c91b1a7744c6c50.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/5379467202d944c99c91b1a7744c6c50.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        title="https://img-blog.csdnimg.cn/5379467202d944c99c91b1a7744c6c50.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16" /></p>
<p>当我们<strong>在右子树插入右孩子导致AVL失衡</strong>时，我们需要进行<strong>单左旋调整</strong>。旋转围绕最小失衡子树的根节点进行。
在删除新节点时也有可能会出现需要单左旋的情况。
左旋代码如下：</p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="k">static</span> <span class="n">node</span> <span class="o">*</span><span class="nf">rotateLeft</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">)</span> <span class="p">{</span>
    <span class="n">node</span> <span class="o">*</span><span class="n">son</span> <span class="o">=</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">;</span>
    <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span> <span class="o">=</span> <span class="n">son</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">;</span>
    <span class="n">son</span><span class="o">-&gt;</span><span class="n">lchild</span> <span class="o">=</span> <span class="n">root</span><span class="p">;</span>
    <span class="n">update_depth</span><span class="p">(</span><span class="n">root</span><span class="p">);</span>
    <span class="n">update_depth</span><span class="p">(</span><span class="n">son</span><span class="p">);</span>
    <span class="k">return</span> <span class="n">son</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div><p><strong>情况二：右旋</strong>
我们继续插入元素{3，2}，此时二叉树为：
<img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/bda47aef11744196994a4357dfa57abd.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        data-srcset="https://img-blog.csdnimg.cn/bda47aef11744196994a4357dfa57abd.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16, https://img-blog.csdnimg.cn/bda47aef11744196994a4357dfa57abd.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 1.5x, https://img-blog.csdnimg.cn/bda47aef11744196994a4357dfa57abd.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/bda47aef11744196994a4357dfa57abd.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        title="https://img-blog.csdnimg.cn/bda47aef11744196994a4357dfa57abd.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16" />
插入3、2后出现了不平衡的情况。此时的插入情况是“<strong>在左子树上插入左孩子导致AVL树失衡</strong>”，我们需要进行单右旋调整。
右旋代码：</p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="k">static</span> <span class="n">node</span> <span class="o">*</span><span class="nf">rotateRight</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">)</span> <span class="p">{</span><span class="c1">//右旋
</span><span class="c1"></span>    <span class="n">node</span> <span class="o">*</span><span class="n">son</span> <span class="o">=</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">;</span>
    <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span> <span class="o">=</span> <span class="n">son</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">;</span>
    <span class="n">son</span><span class="o">-&gt;</span><span class="n">rchild</span> <span class="o">=</span> <span class="n">root</span><span class="p">;</span>
    <span class="n">update_depth</span><span class="p">(</span><span class="n">root</span><span class="p">);</span><span class="c1">//更新深度(右旋只会对这两结点产生影响
</span><span class="c1"></span>    <span class="n">update_depth</span><span class="p">(</span><span class="n">son</span><span class="p">);</span>
    <span class="k">return</span> <span class="n">son</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div><p><strong>情况三：先左旋后右旋</strong>
需要进行两次旋转的原因是第一次旋转后，AVL树仍旧处于不平衡的状态，第二次旋转再次进行调整。
我们继续插入元素{8，7}
<img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/cce694deb68548ebbc3cc93e199a9471.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        data-srcset="https://img-blog.csdnimg.cn/cce694deb68548ebbc3cc93e199a9471.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16, https://img-blog.csdnimg.cn/cce694deb68548ebbc3cc93e199a9471.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 1.5x, https://img-blog.csdnimg.cn/cce694deb68548ebbc3cc93e199a9471.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/cce694deb68548ebbc3cc93e199a9471.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        title="https://img-blog.csdnimg.cn/cce694deb68548ebbc3cc93e199a9471.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16" />
这种情况，总结起来就是“<strong>在右子树上插入左孩子导致AVL树失衡</strong>&quot;,此时我们需要<strong>进行先右旋后左旋的调整</strong>。
调整的代码为：</p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="k">static</span> <span class="n">node</span> <span class="o">*</span><span class="nf">rotateLeftRight</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">)</span> <span class="p">{</span>
    <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span> <span class="o">=</span> <span class="n">rotateLeft</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">);</span>
    <span class="k">return</span> <span class="n">rotateRight</span><span class="p">(</span><span class="n">root</span><span class="p">);</span>
<span class="p">}</span>
</code></pre></div><p>结合例子进行分析：</p>
<ol>
<li>首先对最小不平衡子树的根节点（也就是节点6）的右孩子（也就是8）进行右旋操作</li>
<li>再对节点6进行一次左旋操作</li>
</ol>
<p><strong>情况四：先右旋再左旋</strong>
根据对称性原理，当我们“<strong>在左子树上插入右孩子导致AVL树失衡</strong>&quot;,此时我们需要进行<strong>先左旋后右旋</strong>的调整。如果你不理解接着看图。
我们接着插入节点{0，1}
<img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/da9300544ee84d8cbdfd59577bd9d9a4.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        data-srcset="https://img-blog.csdnimg.cn/da9300544ee84d8cbdfd59577bd9d9a4.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16, https://img-blog.csdnimg.cn/da9300544ee84d8cbdfd59577bd9d9a4.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 1.5x, https://img-blog.csdnimg.cn/da9300544ee84d8cbdfd59577bd9d9a4.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/da9300544ee84d8cbdfd59577bd9d9a4.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        title="https://img-blog.csdnimg.cn/da9300544ee84d8cbdfd59577bd9d9a4.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16" /></p>
<p>调整的代码:</p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="k">static</span> <span class="n">node</span> <span class="o">*</span><span class="nf">rotateRightLeft</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">)</span> <span class="p">{</span>
    <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span> <span class="o">=</span> <span class="n">rotateRight</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">);</span>
    <span class="k">return</span> <span class="n">rotateLeft</span><span class="p">(</span><span class="n">root</span><span class="p">);</span>
<span class="p">}</span>
</code></pre></div><p>结合例子进行分析：</p>
<ol>
<li>首先对最小不平衡子树的根节点（也就是节点2）的左孩子（也就是0）进行左旋操作</li>
<li>再对节点2进行一次右旋操作</li>
</ol>
<p><strong>总结：四种失衡调整</strong>
<img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/d8c8f0e8581d435dbd74285d6b928843.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        data-srcset="https://img-blog.csdnimg.cn/d8c8f0e8581d435dbd74285d6b928843.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16, https://img-blog.csdnimg.cn/d8c8f0e8581d435dbd74285d6b928843.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 1.5x, https://img-blog.csdnimg.cn/d8c8f0e8581d435dbd74285d6b928843.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/d8c8f0e8581d435dbd74285d6b928843.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        title="https://img-blog.csdnimg.cn/d8c8f0e8581d435dbd74285d6b928843.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16" /></p>
<h3 id="7-插入新结点">7. 插入新结点</h3>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="c1">//需要是否兼容相等的元素，可通过对 x&lt;root-&gt;val 或 x&gt;root-&gt;val 这两个中的一个取等号即可
</span><span class="c1"></span><span class="k">static</span> <span class="n">node</span> <span class="o">*</span><span class="nf">Insert</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">,</span> <span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">,</span> <span class="kt">int</span><span class="o">&amp;</span> <span class="n">size</span><span class="p">)</span> <span class="p">{</span> <span class="c1">//所有的deep的更新都在后序遍历后
</span><span class="c1"></span>    <span class="k">if</span> <span class="p">(</span><span class="n">root</span> <span class="o">==</span> <span class="k">nullptr</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">root</span> <span class="o">=</span> <span class="k">new</span> <span class="n">node</span><span class="p">(</span><span class="n">x</span><span class="p">);</span>
        <span class="n">size</span><span class="o">++</span><span class="p">;</span><span class="c1">//创建结点后size++
</span><span class="c1"></span>    <span class="p">}</span> <span class="k">else</span> <span class="k">if</span> <span class="p">(</span><span class="n">x</span> <span class="o">&lt;</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span> <span class="o">=</span> <span class="n">Insert</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">,</span> <span class="n">size</span><span class="p">);</span>
        <span class="c1">//由于在更新该root结点之前，当平衡度未达到该要求之前肯定以及是进行了update_depth操作
</span><span class="c1"></span>        <span class="k">if</span> <span class="p">(</span><span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">)</span> <span class="o">-</span> <span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">)</span> <span class="o">==</span> <span class="mi">2</span><span class="p">)</span>
            <span class="n">root</span> <span class="o">=</span> <span class="n">x</span> <span class="o">&lt;</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="o">-&gt;</span><span class="n">val</span> <span class="o">?</span> <span class="n">rotateRight</span><span class="p">(</span><span class="n">root</span><span class="p">)</span> <span class="o">:</span> <span class="n">rotateLeftRight</span><span class="p">(</span><span class="n">root</span><span class="p">);</span>
    <span class="p">}</span> <span class="k">else</span> <span class="k">if</span> <span class="p">(</span><span class="n">x</span> <span class="o">&gt;</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span> <span class="o">=</span> <span class="n">Insert</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">,</span> <span class="n">size</span><span class="p">);</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">)</span> <span class="o">-</span> <span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">)</span> <span class="o">==</span> <span class="o">-</span><span class="mi">2</span><span class="p">)</span>
            <span class="n">root</span> <span class="o">=</span> <span class="n">x</span> <span class="o">&gt;</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="o">-&gt;</span><span class="n">val</span> <span class="o">?</span> <span class="n">rotateLeft</span><span class="p">(</span><span class="n">root</span><span class="p">)</span> <span class="o">:</span> <span class="n">rotateRightLeft</span><span class="p">(</span><span class="n">root</span><span class="p">);</span>
    <span class="p">}</span>
    <span class="n">update_depth</span><span class="p">(</span><span class="n">root</span><span class="p">);</span>
    <span class="k">return</span> <span class="n">root</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div><h3 id="8-删除结点">8. 删除结点</h3>
<p><strong>失衡的处理</strong>：
删除节点也可能导致AVL树的失衡，实际上删除节点和插入节点是一种互逆的操作：</p>
<ol>
<li>删除<strong>右子树的节点</strong>导致AVL树失衡时，相当于在左子树插入节点导致AVL树失衡，即情况情况二或情况四。</li>
<li>删除<strong>左子树的节点</strong>导致AVL树失衡时，相当于在右子树插入节点导致AVL树失衡，即情况情况一或情况三。</li>
</ol>
<p><strong>维持排序树的处理</strong>：
另外，AVL树也是一棵二叉排序树，因此在删除节点时也要维护二叉排序树的性质。</p>
<ol>
<li>如果删除结点为<strong>叶子结点，则直接删除</strong>，并不会改变搜索树的性质。</li>
<li>如果删除结点<strong>只有左子树或者右子树，则直接把要删除的结点的数据用下一个结点覆盖</strong>，然后删除下一个结点，由于复制了下一层的左右孩子指针，所以不会出现断层的。</li>
<li>如果删除结点<strong>左右子树都有</strong>，则<strong>找出该节点的前驱结点或后继结点的值进行覆盖(不覆盖指针</strong>，这样便仍然是排序二叉树了，然后**继续递归寻找对应的前驱或者后继结点进行删除，**因为左右子树都有，所以它们的前驱或者后继只能是叶子结点，找到直接删除即可。</li>
</ol>
<p>删除处理代码：</p>
<blockquote>
<p>我这里对删除操作进行了进一步优化，如果被删除结点的左右子树都存在，则查看左右子树的高度，如果左边高于右边则选择前驱结点进行删除，反之则后继。</p>
</blockquote>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="k">static</span> <span class="n">node</span> <span class="o">*</span><span class="nf">remove</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">,</span> <span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">,</span> <span class="kt">int</span><span class="o">&amp;</span> <span class="n">size</span><span class="p">)</span> <span class="p">{</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">root</span> <span class="o">==</span> <span class="k">nullptr</span><span class="p">)</span>
        <span class="k">return</span> <span class="k">nullptr</span><span class="p">;</span>

    <span class="k">if</span> <span class="p">(</span><span class="n">x</span> <span class="o">==</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">)</span> <span class="p">{</span>
        <span class="cm">/*左右子树均不为空---用中序的前驱或者后继来进行替换*/</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span> <span class="o">!=</span> <span class="k">nullptr</span> <span class="o">&amp;&amp;</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span> <span class="o">!=</span> <span class="k">nullptr</span><span class="p">)</span> <span class="p">{</span>
            <span class="cm">/*根据左右子树的深度来选择删除替换哪边的*/</span>
            <span class="k">if</span> <span class="p">(</span><span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">)</span> <span class="o">&gt;</span> <span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">))</span> <span class="p">{</span>
                <span class="n">node</span><span class="o">*</span> <span class="n">t</span> <span class="o">=</span> <span class="n">getMaxNode</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">);</span>
                <span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span> <span class="o">=</span> <span class="n">t</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">;</span>
                <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span> <span class="o">=</span> <span class="n">remove</span><span class="p">(</span><span class="n">t</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">,</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">,</span> <span class="n">size</span><span class="p">);</span>
            <span class="p">}</span> <span class="k">else</span> <span class="p">{</span>
                <span class="n">node</span><span class="o">*</span> <span class="n">t</span> <span class="o">=</span> <span class="n">getMinNode</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">);</span>
                <span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span> <span class="o">=</span> <span class="n">t</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">;</span>
                <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span> <span class="o">=</span> <span class="n">remove</span><span class="p">(</span><span class="n">t</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">,</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">,</span> <span class="n">size</span><span class="p">);</span>
            <span class="p">}</span>
        <span class="p">}</span>
        <span class="cm">/*左右子树至少有一个为空的情况，直接往下走一步即可*/</span>
        <span class="k">else</span> <span class="p">{</span>
            <span class="n">node</span><span class="o">*</span> <span class="n">tmp</span> <span class="o">=</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span> <span class="o">==</span> <span class="k">nullptr</span> <span class="o">?</span> <span class="n">root</span><span class="o">-&gt;</span><span class="nl">rchild</span> <span class="p">:</span> <span class="k">nullptr</span><span class="p">;</span>
            <span class="k">if</span> <span class="p">(</span><span class="n">tmp</span> <span class="o">!=</span> <span class="k">nullptr</span><span class="p">)</span> <span class="p">{</span>
                <span class="o">*</span><span class="n">root</span> <span class="o">=</span> <span class="o">*</span><span class="n">tmp</span><span class="p">;</span>
                <span class="k">delete</span> <span class="n">tmp</span><span class="p">;</span>
            <span class="p">}</span>
            <span class="k">else</span> <span class="p">{</span>
                <span class="k">delete</span> <span class="n">root</span><span class="p">;</span>
                <span class="n">root</span> <span class="o">=</span> <span class="k">nullptr</span><span class="p">;</span>
            <span class="p">}</span>
            <span class="c1">//删除时size--
</span><span class="c1"></span>            <span class="n">size</span><span class="o">--</span><span class="p">;</span>
        <span class="p">}</span>
    <span class="p">}</span> <span class="k">else</span> <span class="k">if</span> <span class="p">(</span><span class="n">x</span> <span class="o">&lt;</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span> <span class="o">=</span> <span class="n">remove</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">,</span> <span class="n">size</span><span class="p">);</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">)</span> <span class="o">-</span> <span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">)</span> <span class="o">==</span> <span class="o">-</span><span class="mi">2</span><span class="p">)</span>
            <span class="n">root</span> <span class="o">=</span> <span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">)</span> <span class="o">&gt;</span> <span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">)</span> <span class="o">?</span> <span class="n">rotateRightLeft</span><span class="p">(</span><span class="n">root</span><span class="p">)</span> <span class="o">:</span> <span class="n">rotateLeft</span><span class="p">(</span><span class="n">root</span><span class="p">);</span>
    <span class="p">}</span> <span class="k">else</span> <span class="p">{</span>
        <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span> <span class="o">=</span> <span class="n">remove</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">,</span> <span class="n">size</span><span class="p">);</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">)</span> <span class="o">-</span> <span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">)</span> <span class="o">==</span> <span class="mi">2</span><span class="p">)</span>
            <span class="n">root</span> <span class="o">=</span> <span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">)</span> <span class="o">&gt;</span> <span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">)</span> <span class="o">?</span> <span class="n">rotateLeftRight</span><span class="p">(</span><span class="n">root</span><span class="p">)</span> <span class="o">:</span> <span class="n">rotateRight</span><span class="p">(</span><span class="n">root</span><span class="p">);</span>
    <span class="p">}</span>
    <span class="k">return</span> <span class="n">root</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div><h3 id="9-查找元素">9. 查找元素</h3>
<p>二叉树是一种递归的定义，因此，二叉树的许多操作都可以通过递归简单地实现，例如遍历二叉树、查找指定元素、销毁二叉树等。</p>
<blockquote>
<p>这里使用了迭代方式。</p>
</blockquote>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="kt">bool</span> <span class="nf">find</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">)</span> <span class="p">{</span>
    <span class="c1">//查找直接迭代方式即可
</span><span class="c1"></span>    <span class="n">node</span> <span class="o">*</span><span class="n">f</span> <span class="o">=</span> <span class="n">head</span><span class="p">;</span>
    <span class="k">while</span> <span class="p">(</span><span class="n">f</span> <span class="o">!=</span> <span class="k">nullptr</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">x</span> <span class="o">==</span> <span class="n">f</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">)</span>
            <span class="k">return</span> <span class="nb">true</span><span class="p">;</span>
        <span class="k">else</span> <span class="k">if</span> <span class="p">(</span><span class="n">x</span> <span class="o">&lt;</span> <span class="n">f</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">)</span>
            <span class="n">f</span> <span class="o">=</span> <span class="n">f</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">;</span>
        <span class="k">else</span>
            <span class="n">f</span> <span class="o">=</span> <span class="n">f</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="k">return</span> <span class="nb">false</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div><h3 id="10-遍历二叉树">10. 遍历二叉树</h3>
<ul>
<li>我这里只提供了中序遍历的打印，方便验证二叉搜索树的情况。</li>
</ul>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="k">static</span> <span class="kt">void</span> <span class="nf">inorder</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">)</span> <span class="p">{</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">root</span> <span class="o">!=</span> <span class="k">nullptr</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">inorder</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">);</span>
        <span class="n">printf</span><span class="p">(</span><span class="s">&#34;%d &#34;</span><span class="p">,</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">);</span>
        <span class="n">inorder</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">);</span>
    <span class="p">}</span>
<span class="p">}</span>
</code></pre></div><h3 id="11-avl树的销毁">11. AVL树的销毁</h3>
<p>直接利用后序先处理完左右子树再处理根节点。</p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="k">static</span> <span class="kt">void</span> <span class="nf">destroy</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">)</span> <span class="p">{</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">root</span> <span class="o">==</span> <span class="k">nullptr</span><span class="p">)</span>
        <span class="k">return</span><span class="p">;</span>
    <span class="n">destroy</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">);</span>
    <span class="n">destroy</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">);</span>
    <span class="k">delete</span> <span class="n">root</span><span class="p">;</span>
    <span class="n">root</span> <span class="o">=</span> <span class="k">nullptr</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div><h3 id="12-迭代器的设计">12. 迭代器的设计</h3>
<ul>
<li>关于C++里面的迭代器，其实就是方便遍历容器中的元素，而迭代器需要模拟指针的行为，所以在C++中迭代器其实就是<strong>对指针特别包装的类，对其进行一些运算符的重载即可。</strong></li>
</ul>
<p><strong>内部类充当迭代器</strong></p>
<blockquote>
<p>由于需要满足顺序容器的迭代顺序，所以++和&ndash;操作对应后继和前驱。</p>
</blockquote>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="cm">/*iterator part*/</span>
    <span class="k">class</span> <span class="nc">iterator</span> <span class="p">{</span> <span class="c1">//封装迭代器
</span><span class="c1"></span>        <span class="n">node</span><span class="o">*</span> <span class="n">head</span><span class="p">;</span>
        <span class="n">node</span><span class="o">*</span> <span class="n">root</span><span class="p">;</span>
    <span class="k">public</span><span class="o">:</span>
        <span class="n">iterator</span><span class="p">(</span><span class="n">node</span><span class="o">*</span> <span class="n">head</span><span class="p">,</span> <span class="n">node</span><span class="o">*</span> <span class="n">root</span><span class="p">)</span><span class="o">:</span> <span class="n">head</span><span class="p">(</span><span class="n">head</span><span class="p">),</span> <span class="n">root</span><span class="p">(</span><span class="n">root</span><span class="p">)</span> <span class="p">{}</span>
        <span class="n">iterator</span><span class="o">&amp;</span> <span class="k">operator</span><span class="o">++</span><span class="p">()</span> <span class="p">{</span> <span class="c1">//直接把root加为当前的后继结点
</span><span class="c1"></span>            <span class="n">root</span> <span class="o">=</span> <span class="n">getNext</span><span class="p">(</span><span class="n">head</span><span class="p">,</span> <span class="n">root</span><span class="p">);</span>
            <span class="k">return</span> <span class="o">*</span><span class="k">this</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="kt">bool</span> <span class="k">operator</span><span class="o">==</span><span class="p">(</span><span class="k">const</span> <span class="n">iterator</span><span class="o">&amp;</span> <span class="n">x</span><span class="p">)</span> <span class="p">{</span>
            <span class="k">return</span> <span class="k">this</span><span class="o">-&gt;</span><span class="n">root</span> <span class="o">==</span> <span class="n">x</span><span class="p">.</span><span class="n">root</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="kt">bool</span> <span class="k">operator</span><span class="o">!=</span><span class="p">(</span><span class="k">const</span> <span class="n">iterator</span><span class="o">&amp;</span> <span class="n">x</span><span class="p">)</span> <span class="p">{</span>
            <span class="k">return</span> <span class="k">this</span><span class="o">-&gt;</span><span class="n">root</span> <span class="o">!=</span> <span class="n">x</span><span class="p">.</span><span class="n">root</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="n">iterator</span> <span class="k">operator</span><span class="o">++</span><span class="p">(</span><span class="kt">int</span><span class="p">)</span> <span class="p">{</span>
            <span class="n">iterator</span> <span class="n">t</span> <span class="o">=</span> <span class="o">*</span><span class="k">this</span><span class="p">;</span>
            <span class="n">root</span> <span class="o">=</span> <span class="n">getNext</span><span class="p">(</span><span class="n">head</span><span class="p">,</span> <span class="n">root</span><span class="p">);</span>
            <span class="k">return</span> <span class="n">t</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="n">iterator</span><span class="o">&amp;</span> <span class="k">operator</span><span class="o">--</span><span class="p">()</span> <span class="p">{</span> <span class="c1">//直接把root赋值为前驱结点
</span><span class="c1"></span>            <span class="n">root</span> <span class="o">=</span> <span class="n">getPre</span><span class="p">(</span><span class="n">head</span><span class="p">,</span> <span class="n">root</span><span class="p">);</span>
            <span class="k">return</span> <span class="o">*</span><span class="k">this</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="n">iterator</span> <span class="k">operator</span><span class="o">--</span><span class="p">(</span><span class="kt">int</span><span class="p">)</span> <span class="p">{</span>
            <span class="n">iterator</span> <span class="n">t</span> <span class="o">=</span> <span class="o">*</span><span class="k">this</span><span class="p">;</span>
            <span class="n">root</span> <span class="o">=</span> <span class="n">getPre</span><span class="p">(</span><span class="n">head</span><span class="p">,</span> <span class="n">root</span><span class="p">);</span>
            <span class="k">return</span> <span class="n">t</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="n">node</span><span class="o">&amp;</span> <span class="k">operator</span><span class="o">*</span><span class="p">()</span> <span class="p">{</span> <span class="c1">//解引用的重载
</span><span class="c1"></span>            <span class="k">return</span> <span class="o">*</span><span class="n">root</span><span class="p">;</span>
        <span class="p">}</span>
    <span class="p">};</span>
</code></pre></div><p><strong>外部类提供外界begin()和end()接口得到迭代器的始端和末端</strong></p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp">    <span class="n">iterator</span> <span class="nf">begin</span><span class="p">()</span> <span class="p">{</span>
        <span class="n">node</span><span class="o">*</span> <span class="n">min</span> <span class="o">=</span> <span class="n">getMinNode</span><span class="p">(</span><span class="n">head</span><span class="p">);</span>
        <span class="k">return</span> <span class="n">iterator</span><span class="p">(</span><span class="n">head</span><span class="p">,</span> <span class="n">min</span><span class="p">);</span>
    <span class="p">}</span>
    <span class="n">iterator</span> <span class="nf">end</span><span class="p">()</span> <span class="p">{</span> <span class="c1">//end表示结束标记
</span><span class="c1"></span>        <span class="k">return</span> <span class="n">iterator</span><span class="p">(</span><span class="n">head</span><span class="p">,</span> <span class="k">nullptr</span><span class="p">);</span>
    <span class="p">}</span>
</code></pre></div><h2 id="完整代码">完整代码</h2>
<p><a href="https://github.com/ACking-you" target="_blank" rel="noopener noreffer">我的GitHub</a></p>
<h3 id="avltreeh">AVLTree.h</h3>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="c1">//
</span><span class="c1">// Created by Alone on 2021/10/12.
</span><span class="c1">//
</span><span class="c1"></span><span class="cp">#include</span> <span class="cpf">&lt;algorithm&gt;</span><span class="cp">
</span><span class="cp">#include</span> <span class="cpf">&lt;cstdio&gt;</span><span class="cp">
</span><span class="cp">#include</span> <span class="cpf">&lt;cassert&gt;</span><span class="cp">
</span><span class="cp"></span>
<span class="cp">#ifndef MY_TINY_STL_AVLTREE_H
</span><span class="cp">#define MY_TINY_STL_AVLTREE_H
</span><span class="cp"></span><span class="k">namespace</span> <span class="n">L_B__</span> <span class="p">{</span>
    <span class="k">struct</span> <span class="nc">node</span> <span class="p">{</span>
        <span class="kt">int</span> <span class="n">val</span><span class="p">;</span>
        <span class="kt">int</span> <span class="n">depth</span><span class="p">;</span>
        <span class="n">node</span> <span class="o">*</span><span class="n">lchild</span><span class="p">;</span>
        <span class="n">node</span> <span class="o">*</span><span class="n">rchild</span><span class="p">;</span>

        <span class="n">node</span><span class="p">()</span> <span class="o">:</span> <span class="n">val</span><span class="p">(</span><span class="mi">0</span><span class="p">),</span> <span class="n">lchild</span><span class="p">(</span><span class="k">nullptr</span><span class="p">),</span> <span class="n">rchild</span><span class="p">(</span><span class="k">nullptr</span><span class="p">)</span> <span class="p">{}</span>

        <span class="n">node</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">)</span> <span class="o">:</span> <span class="n">val</span><span class="p">(</span><span class="n">x</span><span class="p">),</span> <span class="n">lchild</span><span class="p">(</span><span class="k">nullptr</span><span class="p">),</span> <span class="n">rchild</span><span class="p">(</span><span class="k">nullptr</span><span class="p">)</span> <span class="p">{}</span>
    <span class="p">};</span>

    <span class="k">class</span> <span class="nc">AVLTree</span> <span class="p">{</span>
        <span class="cm">/*date part*/</span>
        <span class="n">node</span> <span class="o">*</span><span class="n">head</span><span class="p">;</span>
        <span class="kt">int</span> <span class="n">length</span><span class="p">;</span>
    <span class="k">public</span><span class="o">:</span>
        <span class="cm">/*construct and destruct part*/</span>
        <span class="n">AVLTree</span><span class="p">()</span> <span class="o">:</span> <span class="n">head</span><span class="p">(</span><span class="k">nullptr</span><span class="p">),</span> <span class="n">length</span><span class="p">(</span><span class="mi">0</span><span class="p">)</span> <span class="p">{}</span>

        <span class="n">AVLTree</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">)</span> <span class="o">:</span> <span class="n">head</span><span class="p">(</span><span class="k">new</span> <span class="n">node</span><span class="p">(</span><span class="n">x</span><span class="p">)),</span> <span class="n">length</span><span class="p">(</span><span class="mi">1</span><span class="p">)</span> <span class="p">{}</span>

        <span class="o">~</span><span class="n">AVLTree</span><span class="p">()</span> <span class="p">{</span>
            <span class="n">destroy</span><span class="p">(</span><span class="n">head</span><span class="p">);</span>
        <span class="p">}</span>

    <span class="k">public</span><span class="o">:</span>
        <span class="cm">/*iterator part*/</span>
        <span class="k">class</span> <span class="nc">iterator</span> <span class="p">{</span><span class="c1">//封装迭代器：内部类--只能调用外部类的静态函数
</span><span class="c1"></span>            <span class="n">node</span> <span class="o">*</span><span class="n">head</span><span class="p">;</span>
            <span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">;</span>
        <span class="k">public</span><span class="o">:</span>
            <span class="n">iterator</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">head</span><span class="p">,</span> <span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">)</span> <span class="o">:</span> <span class="n">head</span><span class="p">(</span><span class="n">head</span><span class="p">),</span> <span class="n">root</span><span class="p">(</span><span class="n">root</span><span class="p">)</span> <span class="p">{}</span>

            <span class="n">iterator</span> <span class="o">&amp;</span><span class="k">operator</span><span class="o">++</span><span class="p">();</span>

            <span class="kt">bool</span> <span class="k">operator</span><span class="o">==</span><span class="p">(</span><span class="k">const</span> <span class="n">iterator</span> <span class="o">&amp;</span><span class="n">x</span><span class="p">);</span>

            <span class="kt">bool</span> <span class="k">operator</span><span class="o">!=</span><span class="p">(</span><span class="k">const</span> <span class="n">iterator</span> <span class="o">&amp;</span><span class="n">x</span><span class="p">);</span>

            <span class="n">iterator</span> <span class="k">operator</span><span class="o">++</span><span class="p">(</span><span class="kt">int</span><span class="p">);</span>

            <span class="n">iterator</span> <span class="o">&amp;</span><span class="k">operator</span><span class="o">--</span><span class="p">();</span>

            <span class="n">iterator</span> <span class="k">operator</span><span class="o">--</span><span class="p">(</span><span class="kt">int</span><span class="p">);</span>

            <span class="kt">int</span> <span class="k">operator</span><span class="o">*</span><span class="p">();</span>
        <span class="p">};</span>

    <span class="k">private</span><span class="o">:</span>
        <span class="cm">/*static member function*/</span>
        <span class="cm">/*Rotate Part*/</span>
        <span class="k">static</span> <span class="n">node</span> <span class="o">*</span><span class="n">rotateRight</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">);</span>

        <span class="k">static</span> <span class="n">node</span> <span class="o">*</span><span class="nf">rotateLeft</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">);</span>

        <span class="k">static</span> <span class="n">node</span> <span class="o">*</span><span class="nf">rotateLeftRight</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">);</span>

        <span class="k">static</span> <span class="n">node</span> <span class="o">*</span><span class="nf">rotateRightLeft</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">);</span>

        <span class="cm">/*Destruct*/</span>
        <span class="k">static</span> <span class="kt">void</span> <span class="nf">destroy</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">);</span>

        <span class="cm">/*Getter*/</span>
        <span class="k">static</span> <span class="n">node</span> <span class="o">*</span><span class="nf">getNext</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">,</span> <span class="n">node</span> <span class="o">*</span><span class="n">p</span><span class="p">);</span>

        <span class="k">static</span> <span class="n">node</span> <span class="o">*</span><span class="nf">getPre</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">,</span> <span class="n">node</span> <span class="o">*</span><span class="n">p</span><span class="p">);</span>

        <span class="k">static</span> <span class="n">node</span> <span class="o">*</span><span class="nf">getMinNode</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">);</span>

        <span class="k">static</span> <span class="n">node</span> <span class="o">*</span><span class="nf">getMaxNode</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">);</span>

        <span class="k">static</span> <span class="kt">int</span> <span class="nf">get_depth</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">);</span>

        <span class="k">static</span> <span class="kt">void</span> <span class="nf">update_depth</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">);</span>

        <span class="cm">/*Insert&amp;Remove*/</span>
        <span class="k">static</span> <span class="n">node</span> <span class="o">*</span><span class="nf">Insert</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">,</span> <span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">,</span> <span class="kt">int</span> <span class="o">&amp;</span><span class="n">size</span><span class="p">);</span>

        <span class="k">static</span> <span class="n">node</span> <span class="o">*</span><span class="nf">remove</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">,</span> <span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">,</span> <span class="kt">int</span> <span class="o">&amp;</span><span class="n">size</span><span class="p">);</span>

        <span class="cm">/*print_order*/</span>
        <span class="k">static</span> <span class="kt">void</span> <span class="nf">inorder</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">);</span>

    <span class="k">public</span><span class="o">:</span>
        <span class="cm">/*public interface*/</span>
        <span class="cm">/*clear&amp;empty*/</span>
        <span class="kt">void</span> <span class="n">clear</span><span class="p">();</span>

        <span class="kt">bool</span> <span class="nf">isEmpty</span><span class="p">();</span>

        <span class="cm">/*find*/</span>
        <span class="kt">bool</span> <span class="nf">find</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">);</span>

        <span class="cm">/*insert&amp;remove*/</span>
        <span class="kt">void</span> <span class="nf">insert</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">);</span>

        <span class="kt">void</span> <span class="nf">remove</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">);</span>

        <span class="cm">/*size*/</span>
        <span class="kt">int</span> <span class="nf">size</span><span class="p">();</span>

        <span class="cm">/*begin&amp;end*/</span>
        <span class="n">iterator</span> <span class="nf">begin</span><span class="p">();</span>

        <span class="n">iterator</span> <span class="nf">end</span><span class="p">();</span>

        <span class="cm">/*print*/</span>
        <span class="kt">void</span> <span class="nf">inorder_print</span><span class="p">();</span>
    <span class="p">};</span>
<span class="p">}</span>


<span class="cp">#endif </span><span class="c1">//MY_TINY_STL_AVLTREE_H
</span></code></pre></div><h3 id="avltreecpp">AVLTree.cpp</h3>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="c1">//
</span><span class="c1">// Created by Alone on 2021/10/12.
</span><span class="c1">//
</span><span class="c1"></span>
<span class="cp">#include</span> <span class="cpf">&#34;AVLTree.h&#34;</span><span class="cp">
</span><span class="cp"></span>
<span class="cm">/*Rotate*/</span>
<span class="n">L_B__</span><span class="o">::</span><span class="n">node</span> <span class="o">*</span><span class="n">L_B__</span><span class="o">::</span><span class="n">AVLTree</span><span class="o">::</span><span class="n">rotateRight</span><span class="p">(</span><span class="n">L_B__</span><span class="o">::</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">)</span> <span class="p">{</span><span class="c1">//右旋
</span><span class="c1"></span>    <span class="n">node</span> <span class="o">*</span><span class="n">son</span> <span class="o">=</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">;</span>
    <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span> <span class="o">=</span> <span class="n">son</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">;</span>
    <span class="n">son</span><span class="o">-&gt;</span><span class="n">rchild</span> <span class="o">=</span> <span class="n">root</span><span class="p">;</span>
    <span class="n">update_depth</span><span class="p">(</span><span class="n">root</span><span class="p">);</span><span class="c1">//更新深度(右旋只会对这两结点产生影响
</span><span class="c1"></span>    <span class="n">update_depth</span><span class="p">(</span><span class="n">son</span><span class="p">);</span>
    <span class="k">return</span> <span class="n">son</span><span class="p">;</span>
<span class="p">}</span>

<span class="n">L_B__</span><span class="o">::</span><span class="n">node</span> <span class="o">*</span><span class="n">L_B__</span><span class="o">::</span><span class="n">AVLTree</span><span class="o">::</span><span class="n">rotateLeft</span><span class="p">(</span><span class="n">L_B__</span><span class="o">::</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">)</span> <span class="p">{</span>
    <span class="n">node</span> <span class="o">*</span><span class="n">son</span> <span class="o">=</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">;</span>
    <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span> <span class="o">=</span> <span class="n">son</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">;</span>
    <span class="n">son</span><span class="o">-&gt;</span><span class="n">lchild</span> <span class="o">=</span> <span class="n">root</span><span class="p">;</span>
    <span class="n">update_depth</span><span class="p">(</span><span class="n">root</span><span class="p">);</span>
    <span class="n">update_depth</span><span class="p">(</span><span class="n">son</span><span class="p">);</span>
    <span class="k">return</span> <span class="n">son</span><span class="p">;</span>
<span class="p">}</span>

<span class="n">L_B__</span><span class="o">::</span><span class="n">node</span> <span class="o">*</span><span class="n">L_B__</span><span class="o">::</span><span class="n">AVLTree</span><span class="o">::</span><span class="n">rotateLeftRight</span><span class="p">(</span><span class="n">L_B__</span><span class="o">::</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">)</span> <span class="p">{</span>
    <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span> <span class="o">=</span> <span class="n">rotateLeft</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">);</span>
    <span class="k">return</span> <span class="nf">rotateRight</span><span class="p">(</span><span class="n">root</span><span class="p">);</span>
<span class="p">}</span>

<span class="n">L_B__</span><span class="o">::</span><span class="n">node</span> <span class="o">*</span><span class="n">L_B__</span><span class="o">::</span><span class="n">AVLTree</span><span class="o">::</span><span class="n">rotateRightLeft</span><span class="p">(</span><span class="n">L_B__</span><span class="o">::</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">)</span> <span class="p">{</span>
    <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span> <span class="o">=</span> <span class="n">rotateRight</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">);</span>
    <span class="k">return</span> <span class="nf">rotateLeft</span><span class="p">(</span><span class="n">root</span><span class="p">);</span>
<span class="p">}</span>


<span class="cm">/*Destruct*/</span>
<span class="kt">void</span> <span class="n">L_B__</span><span class="o">::</span><span class="n">AVLTree</span><span class="o">::</span><span class="n">destroy</span><span class="p">(</span><span class="n">L_B__</span><span class="o">::</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">)</span> <span class="p">{</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">root</span> <span class="o">==</span> <span class="k">nullptr</span><span class="p">)</span>
        <span class="k">return</span><span class="p">;</span>
    <span class="n">destroy</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">);</span>
    <span class="n">destroy</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">);</span>
    <span class="k">delete</span> <span class="n">root</span><span class="p">;</span>
    <span class="n">root</span> <span class="o">=</span> <span class="k">nullptr</span><span class="p">;</span>
<span class="p">}</span>


<span class="cm">/*Getter*/</span>
<span class="n">L_B__</span><span class="o">::</span><span class="n">node</span> <span class="o">*</span><span class="n">L_B__</span><span class="o">::</span><span class="n">AVLTree</span><span class="o">::</span><span class="n">getNext</span><span class="p">(</span><span class="n">L_B__</span><span class="o">::</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">,</span> <span class="n">L_B__</span><span class="o">::</span><span class="n">node</span> <span class="o">*</span><span class="n">p</span><span class="p">)</span> <span class="p">{</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">root</span> <span class="o">==</span> <span class="k">nullptr</span> <span class="o">||</span> <span class="n">p</span> <span class="o">==</span> <span class="k">nullptr</span><span class="p">)</span> <span class="k">return</span> <span class="k">nullptr</span><span class="p">;</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">p</span><span class="o">-&gt;</span><span class="n">val</span> <span class="o">&gt;=</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">return</span> <span class="nf">getNext</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">,</span> <span class="n">p</span><span class="p">);</span>
    <span class="p">}</span> <span class="k">else</span> <span class="p">{</span>
        <span class="n">node</span> <span class="o">*</span><span class="n">left</span> <span class="o">=</span> <span class="n">getNext</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">,</span> <span class="n">p</span><span class="p">);</span>
        <span class="k">return</span> <span class="n">left</span> <span class="o">?</span> <span class="nl">left</span> <span class="p">:</span> <span class="n">root</span><span class="p">;</span>
    <span class="p">}</span>
<span class="p">}</span>

<span class="n">L_B__</span><span class="o">::</span><span class="n">node</span> <span class="o">*</span><span class="n">L_B__</span><span class="o">::</span><span class="n">AVLTree</span><span class="o">::</span><span class="n">getPre</span><span class="p">(</span><span class="n">L_B__</span><span class="o">::</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">,</span> <span class="n">L_B__</span><span class="o">::</span><span class="n">node</span> <span class="o">*</span><span class="n">p</span><span class="p">)</span> <span class="p">{</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">root</span> <span class="o">==</span> <span class="k">nullptr</span> <span class="o">||</span> <span class="n">p</span> <span class="o">==</span> <span class="k">nullptr</span><span class="p">)</span><span class="k">return</span> <span class="k">nullptr</span><span class="p">;</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">p</span><span class="o">-&gt;</span><span class="n">val</span> <span class="o">&lt;=</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">return</span> <span class="nf">getPre</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">,</span> <span class="n">p</span><span class="p">);</span>
    <span class="p">}</span> <span class="k">else</span> <span class="p">{</span>
        <span class="n">node</span> <span class="o">*</span><span class="n">right</span> <span class="o">=</span> <span class="n">getPre</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">,</span> <span class="n">p</span><span class="p">);</span>
        <span class="k">return</span> <span class="n">right</span> <span class="o">?</span> <span class="nl">right</span> <span class="p">:</span> <span class="n">root</span><span class="p">;</span>
    <span class="p">}</span>
<span class="p">}</span>

<span class="n">L_B__</span><span class="o">::</span><span class="n">node</span> <span class="o">*</span><span class="n">L_B__</span><span class="o">::</span><span class="n">AVLTree</span><span class="o">::</span><span class="n">getMinNode</span><span class="p">(</span><span class="n">L_B__</span><span class="o">::</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">)</span> <span class="p">{</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">root</span> <span class="o">==</span> <span class="k">nullptr</span><span class="p">)</span>
        <span class="k">return</span> <span class="k">nullptr</span><span class="p">;</span>
    <span class="k">while</span> <span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span> <span class="o">!=</span> <span class="k">nullptr</span><span class="p">)</span>
        <span class="n">root</span> <span class="o">=</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">;</span>
    <span class="k">return</span> <span class="n">root</span><span class="p">;</span>
<span class="p">}</span>

<span class="n">L_B__</span><span class="o">::</span><span class="n">node</span> <span class="o">*</span><span class="n">L_B__</span><span class="o">::</span><span class="n">AVLTree</span><span class="o">::</span><span class="n">getMaxNode</span><span class="p">(</span><span class="n">L_B__</span><span class="o">::</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">)</span> <span class="p">{</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">root</span> <span class="o">==</span> <span class="k">nullptr</span><span class="p">)</span>
        <span class="k">return</span> <span class="k">nullptr</span><span class="p">;</span>
    <span class="k">while</span> <span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span> <span class="o">!=</span> <span class="k">nullptr</span><span class="p">)</span>
        <span class="n">root</span> <span class="o">=</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">;</span>
    <span class="k">return</span> <span class="n">root</span><span class="p">;</span>
<span class="p">}</span>

<span class="kt">int</span> <span class="n">L_B__</span><span class="o">::</span><span class="n">AVLTree</span><span class="o">::</span><span class="n">get_depth</span><span class="p">(</span><span class="n">L_B__</span><span class="o">::</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">)</span> <span class="p">{</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">root</span> <span class="o">==</span> <span class="k">nullptr</span><span class="p">)</span>
        <span class="k">return</span> <span class="mi">0</span><span class="p">;</span>
    <span class="k">return</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">depth</span><span class="p">;</span>
<span class="p">}</span>

<span class="kt">void</span> <span class="n">L_B__</span><span class="o">::</span><span class="n">AVLTree</span><span class="o">::</span><span class="n">update_depth</span><span class="p">(</span><span class="n">L_B__</span><span class="o">::</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">)</span> <span class="p">{</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">root</span> <span class="o">==</span> <span class="k">nullptr</span><span class="p">)</span>
        <span class="k">return</span><span class="p">;</span>
    <span class="n">root</span><span class="o">-&gt;</span><span class="n">depth</span> <span class="o">=</span> <span class="n">std</span><span class="o">::</span><span class="n">max</span><span class="p">(</span><span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">),</span> <span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">))</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span>
<span class="p">}</span>


<span class="cm">/*Insert&amp;remove*/</span>
<span class="n">L_B__</span><span class="o">::</span><span class="n">node</span> <span class="o">*</span><span class="n">L_B__</span><span class="o">::</span><span class="n">AVLTree</span><span class="o">::</span><span class="n">Insert</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">,</span> <span class="n">L_B__</span><span class="o">::</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">,</span> <span class="kt">int</span> <span class="o">&amp;</span><span class="n">size</span><span class="p">)</span> <span class="p">{</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">root</span> <span class="o">==</span> <span class="k">nullptr</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">root</span> <span class="o">=</span> <span class="k">new</span> <span class="n">node</span><span class="p">(</span><span class="n">x</span><span class="p">);</span>
        <span class="n">size</span><span class="o">++</span><span class="p">;</span><span class="c1">//创建结点后size++
</span><span class="c1"></span>    <span class="p">}</span> <span class="k">else</span> <span class="nf">if</span> <span class="p">(</span><span class="n">x</span> <span class="o">&lt;</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span> <span class="o">=</span> <span class="n">Insert</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">,</span> <span class="n">size</span><span class="p">);</span>
        <span class="c1">//由于在更新该root结点之前，当平衡度未达到该要求之前肯定以及是进行了update_depth操作
</span><span class="c1"></span>        <span class="k">if</span> <span class="p">(</span><span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">)</span> <span class="o">-</span> <span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">)</span> <span class="o">==</span> <span class="mi">2</span><span class="p">)</span>
            <span class="n">root</span> <span class="o">=</span> <span class="n">x</span> <span class="o">&lt;</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="o">-&gt;</span><span class="n">val</span> <span class="o">?</span> <span class="n">rotateRight</span><span class="p">(</span><span class="n">root</span><span class="p">)</span> <span class="o">:</span> <span class="n">rotateLeftRight</span><span class="p">(</span><span class="n">root</span><span class="p">);</span>
    <span class="p">}</span> <span class="k">else</span> <span class="nf">if</span> <span class="p">(</span><span class="n">x</span> <span class="o">&gt;</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span> <span class="o">=</span> <span class="n">Insert</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">,</span> <span class="n">size</span><span class="p">);</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">)</span> <span class="o">-</span> <span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">)</span> <span class="o">==</span> <span class="o">-</span><span class="mi">2</span><span class="p">)</span>
            <span class="n">root</span> <span class="o">=</span> <span class="n">x</span> <span class="o">&gt;</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="o">-&gt;</span><span class="n">val</span> <span class="o">?</span> <span class="n">rotateLeft</span><span class="p">(</span><span class="n">root</span><span class="p">)</span> <span class="o">:</span> <span class="n">rotateRightLeft</span><span class="p">(</span><span class="n">root</span><span class="p">);</span>
    <span class="p">}</span>
    <span class="n">update_depth</span><span class="p">(</span><span class="n">root</span><span class="p">);</span>
    <span class="k">return</span> <span class="n">root</span><span class="p">;</span>
<span class="p">}</span>

<span class="n">L_B__</span><span class="o">::</span><span class="n">node</span> <span class="o">*</span><span class="n">L_B__</span><span class="o">::</span><span class="n">AVLTree</span><span class="o">::</span><span class="n">remove</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">,</span> <span class="n">L_B__</span><span class="o">::</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">,</span> <span class="kt">int</span> <span class="o">&amp;</span><span class="n">size</span><span class="p">)</span> <span class="p">{</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">root</span> <span class="o">==</span> <span class="k">nullptr</span><span class="p">)</span>
        <span class="k">return</span> <span class="k">nullptr</span><span class="p">;</span>

    <span class="k">if</span> <span class="p">(</span><span class="n">x</span> <span class="o">==</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">)</span> <span class="p">{</span>
        <span class="cm">/*左右子树均不为空---用中序的前驱或者后继来进行替换*/</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span> <span class="o">!=</span> <span class="k">nullptr</span> <span class="o">&amp;&amp;</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span> <span class="o">!=</span> <span class="k">nullptr</span><span class="p">)</span> <span class="p">{</span>
            <span class="cm">/*根据左右子树的深度来选择删除替换哪边的*/</span>
            <span class="k">if</span> <span class="p">(</span><span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">)</span> <span class="o">&gt;</span> <span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">))</span> <span class="p">{</span>
                <span class="n">node</span> <span class="o">*</span><span class="n">t</span> <span class="o">=</span> <span class="n">getMaxNode</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">);</span>
                <span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span> <span class="o">=</span> <span class="n">t</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">;</span>
                <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span> <span class="o">=</span> <span class="n">remove</span><span class="p">(</span><span class="n">t</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">,</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">,</span> <span class="n">size</span><span class="p">);</span>
            <span class="p">}</span> <span class="k">else</span> <span class="p">{</span>
                <span class="n">node</span> <span class="o">*</span><span class="n">t</span> <span class="o">=</span> <span class="n">getMinNode</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">);</span>
                <span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span> <span class="o">=</span> <span class="n">t</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">;</span>
                <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span> <span class="o">=</span> <span class="n">remove</span><span class="p">(</span><span class="n">t</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">,</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">,</span> <span class="n">size</span><span class="p">);</span>
            <span class="p">}</span>
        <span class="p">}</span>
            <span class="cm">/*左右子树至少有一个为空的情况，直接往下走一步即可*/</span>
        <span class="k">else</span> <span class="p">{</span>
            <span class="n">node</span> <span class="o">*</span><span class="n">tmp</span> <span class="o">=</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span> <span class="o">==</span> <span class="k">nullptr</span> <span class="o">?</span> <span class="n">root</span><span class="o">-&gt;</span><span class="nl">rchild</span> <span class="p">:</span> <span class="k">nullptr</span><span class="p">;</span>
            <span class="k">if</span> <span class="p">(</span><span class="n">tmp</span> <span class="o">!=</span> <span class="k">nullptr</span><span class="p">)</span> <span class="p">{</span>
                <span class="o">*</span><span class="n">root</span> <span class="o">=</span> <span class="o">*</span><span class="n">tmp</span><span class="p">;</span>
                <span class="k">delete</span> <span class="n">tmp</span><span class="p">;</span>
            <span class="p">}</span> <span class="k">else</span> <span class="p">{</span>
                <span class="k">delete</span> <span class="n">root</span><span class="p">;</span>
                <span class="n">root</span> <span class="o">=</span> <span class="k">nullptr</span><span class="p">;</span>
            <span class="p">}</span>
            <span class="c1">//删除时size--
</span><span class="c1"></span>            <span class="n">size</span><span class="o">--</span><span class="p">;</span>
        <span class="p">}</span>
    <span class="p">}</span> <span class="k">else</span> <span class="nf">if</span> <span class="p">(</span><span class="n">x</span> <span class="o">&lt;</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span> <span class="o">=</span> <span class="n">remove</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">,</span> <span class="n">size</span><span class="p">);</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">)</span> <span class="o">-</span> <span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">)</span> <span class="o">==</span> <span class="o">-</span><span class="mi">2</span><span class="p">)</span>
            <span class="n">root</span> <span class="o">=</span> <span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">)</span> <span class="o">&gt;</span> <span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">)</span> <span class="o">?</span> <span class="n">rotateRightLeft</span><span class="p">(</span><span class="n">root</span><span class="p">)</span>
                                                                                     <span class="o">:</span> <span class="n">rotateLeft</span><span class="p">(</span><span class="n">root</span><span class="p">);</span>
    <span class="p">}</span> <span class="k">else</span> <span class="p">{</span>
        <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span> <span class="o">=</span> <span class="n">remove</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">,</span> <span class="n">size</span><span class="p">);</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">)</span> <span class="o">-</span> <span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">)</span> <span class="o">==</span> <span class="mi">2</span><span class="p">)</span>
            <span class="n">root</span> <span class="o">=</span> <span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">)</span> <span class="o">&gt;</span> <span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">)</span> <span class="o">?</span> <span class="n">rotateLeftRight</span><span class="p">(</span><span class="n">root</span><span class="p">)</span>
                                                                                     <span class="o">:</span> <span class="n">rotateRight</span><span class="p">(</span><span class="n">root</span><span class="p">);</span>
    <span class="p">}</span>
    <span class="k">return</span> <span class="n">root</span><span class="p">;</span>
<span class="p">}</span>


<span class="cm">/*print part*/</span>
<span class="kt">void</span> <span class="n">L_B__</span><span class="o">::</span><span class="n">AVLTree</span><span class="o">::</span><span class="n">inorder</span><span class="p">(</span><span class="n">L_B__</span><span class="o">::</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">)</span> <span class="p">{</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">root</span> <span class="o">!=</span> <span class="k">nullptr</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">inorder</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">);</span>
        <span class="n">printf</span><span class="p">(</span><span class="s">&#34;%d &#34;</span><span class="p">,</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">);</span>
        <span class="n">inorder</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">);</span>
    <span class="p">}</span>
<span class="p">}</span>


<span class="cm">/*clear&amp;isEmpty*/</span>
<span class="kt">void</span> <span class="n">L_B__</span><span class="o">::</span><span class="n">AVLTree</span><span class="o">::</span><span class="n">clear</span><span class="p">()</span> <span class="p">{</span>
    <span class="n">destroy</span><span class="p">(</span><span class="n">head</span><span class="p">);</span>
<span class="p">}</span>

<span class="kt">bool</span> <span class="n">L_B__</span><span class="o">::</span><span class="n">AVLTree</span><span class="o">::</span><span class="n">isEmpty</span><span class="p">()</span> <span class="p">{</span>
    <span class="k">return</span> <span class="n">head</span> <span class="o">==</span> <span class="k">nullptr</span><span class="p">;</span>
<span class="p">}</span>


<span class="cm">/*find*/</span>
<span class="kt">bool</span> <span class="n">L_B__</span><span class="o">::</span><span class="n">AVLTree</span><span class="o">::</span><span class="n">find</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">)</span> <span class="p">{</span>
    <span class="c1">//查找直接迭代方式即可
</span><span class="c1"></span>    <span class="n">node</span> <span class="o">*</span><span class="n">f</span> <span class="o">=</span> <span class="n">head</span><span class="p">;</span>
    <span class="k">while</span> <span class="p">(</span><span class="n">f</span> <span class="o">!=</span> <span class="k">nullptr</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">x</span> <span class="o">==</span> <span class="n">f</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">)</span>
            <span class="k">return</span> <span class="nb">true</span><span class="p">;</span>
        <span class="k">else</span> <span class="nf">if</span> <span class="p">(</span><span class="n">x</span> <span class="o">&lt;</span> <span class="n">f</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">)</span>
            <span class="n">f</span> <span class="o">=</span> <span class="n">f</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">;</span>
        <span class="k">else</span>
            <span class="n">f</span> <span class="o">=</span> <span class="n">f</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="k">return</span> <span class="nb">false</span><span class="p">;</span>
<span class="p">}</span>


<span class="cm">/*insert&amp;remove*/</span>
<span class="kt">void</span> <span class="n">L_B__</span><span class="o">::</span><span class="n">AVLTree</span><span class="o">::</span><span class="n">insert</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">)</span> <span class="p">{</span>
    <span class="n">head</span> <span class="o">=</span> <span class="n">Insert</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">head</span><span class="p">,</span> <span class="n">length</span><span class="p">);</span>
<span class="p">}</span>

<span class="kt">void</span> <span class="n">L_B__</span><span class="o">::</span><span class="n">AVLTree</span><span class="o">::</span><span class="n">remove</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">)</span> <span class="p">{</span>
    <span class="n">assert</span><span class="p">(</span><span class="n">length</span> <span class="o">!=</span> <span class="mi">0</span><span class="p">);</span>
    <span class="n">head</span> <span class="o">=</span> <span class="n">remove</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">head</span><span class="p">,</span> <span class="n">length</span><span class="p">);</span>
<span class="p">}</span>

<span class="kt">int</span> <span class="n">L_B__</span><span class="o">::</span><span class="n">AVLTree</span><span class="o">::</span><span class="n">size</span><span class="p">()</span> <span class="p">{</span>
    <span class="k">return</span> <span class="n">length</span><span class="p">;</span>
<span class="p">}</span>


<span class="cm">/*begin&amp;end*/</span>
<span class="n">L_B__</span><span class="o">::</span><span class="n">AVLTree</span><span class="o">::</span><span class="n">iterator</span> <span class="n">L_B__</span><span class="o">::</span><span class="n">AVLTree</span><span class="o">::</span><span class="n">begin</span><span class="p">()</span> <span class="p">{</span>
    <span class="n">node</span> <span class="o">*</span><span class="n">min</span> <span class="o">=</span> <span class="n">getMinNode</span><span class="p">(</span><span class="n">head</span><span class="p">);</span>
    <span class="k">return</span> <span class="nf">iterator</span><span class="p">(</span><span class="n">head</span><span class="p">,</span> <span class="n">min</span><span class="p">);</span>
<span class="p">}</span>

<span class="n">L_B__</span><span class="o">::</span><span class="n">AVLTree</span><span class="o">::</span><span class="n">iterator</span> <span class="n">L_B__</span><span class="o">::</span><span class="n">AVLTree</span><span class="o">::</span><span class="n">end</span><span class="p">()</span> <span class="p">{</span>
    <span class="k">return</span> <span class="nf">iterator</span><span class="p">(</span><span class="n">head</span><span class="p">,</span> <span class="k">nullptr</span><span class="p">);</span>
<span class="p">}</span>

<span class="cm">/*print*/</span>
<span class="kt">void</span> <span class="n">L_B__</span><span class="o">::</span><span class="n">AVLTree</span><span class="o">::</span><span class="n">inorder_print</span><span class="p">()</span> <span class="p">{</span>
    <span class="n">printf</span><span class="p">(</span><span class="s">&#34;Inorder:# &#34;</span><span class="p">);</span>
    <span class="n">inorder</span><span class="p">(</span><span class="n">head</span><span class="p">);</span>
<span class="p">}</span>


<span class="cm">/*iterator implement*/</span>
<span class="kt">bool</span> <span class="n">L_B__</span><span class="o">::</span><span class="n">AVLTree</span><span class="o">::</span><span class="n">iterator</span><span class="o">::</span><span class="k">operator</span><span class="o">==</span><span class="p">(</span><span class="k">const</span> <span class="n">L_B__</span><span class="o">::</span><span class="n">AVLTree</span><span class="o">::</span><span class="n">iterator</span> <span class="o">&amp;</span><span class="n">x</span><span class="p">)</span> <span class="p">{</span>
    <span class="k">return</span> <span class="k">this</span><span class="o">-&gt;</span><span class="n">root</span> <span class="o">==</span> <span class="n">x</span><span class="p">.</span><span class="n">root</span><span class="p">;</span>
<span class="p">}</span>

<span class="kt">bool</span> <span class="n">L_B__</span><span class="o">::</span><span class="n">AVLTree</span><span class="o">::</span><span class="n">iterator</span><span class="o">::</span><span class="k">operator</span><span class="o">!=</span><span class="p">(</span><span class="k">const</span> <span class="n">L_B__</span><span class="o">::</span><span class="n">AVLTree</span><span class="o">::</span><span class="n">iterator</span> <span class="o">&amp;</span><span class="n">x</span><span class="p">)</span> <span class="p">{</span>
    <span class="k">return</span> <span class="k">this</span><span class="o">-&gt;</span><span class="n">root</span> <span class="o">!=</span> <span class="n">x</span><span class="p">.</span><span class="n">root</span><span class="p">;</span>
<span class="p">}</span>

<span class="n">L_B__</span><span class="o">::</span><span class="n">AVLTree</span><span class="o">::</span><span class="n">iterator</span> <span class="n">L_B__</span><span class="o">::</span><span class="n">AVLTree</span><span class="o">::</span><span class="n">iterator</span><span class="o">::</span><span class="k">operator</span><span class="o">++</span><span class="p">(</span><span class="kt">int</span><span class="p">)</span> <span class="p">{</span>
    <span class="n">iterator</span> <span class="n">t</span> <span class="o">=</span> <span class="o">*</span><span class="k">this</span><span class="p">;</span>
    <span class="n">root</span> <span class="o">=</span> <span class="n">getNext</span><span class="p">(</span><span class="n">head</span><span class="p">,</span> <span class="n">root</span><span class="p">);</span>
    <span class="k">return</span> <span class="n">t</span><span class="p">;</span>
<span class="p">}</span>

<span class="n">L_B__</span><span class="o">::</span><span class="n">AVLTree</span><span class="o">::</span><span class="n">iterator</span> <span class="o">&amp;</span><span class="n">L_B__</span><span class="o">::</span><span class="n">AVLTree</span><span class="o">::</span><span class="n">iterator</span><span class="o">::</span><span class="k">operator</span><span class="o">--</span><span class="p">()</span> <span class="p">{</span>
    <span class="n">root</span> <span class="o">=</span> <span class="n">getPre</span><span class="p">(</span><span class="n">head</span><span class="p">,</span> <span class="n">root</span><span class="p">);</span>
    <span class="k">return</span> <span class="o">*</span><span class="k">this</span><span class="p">;</span>
<span class="p">}</span>

<span class="n">L_B__</span><span class="o">::</span><span class="n">AVLTree</span><span class="o">::</span><span class="n">iterator</span> <span class="n">L_B__</span><span class="o">::</span><span class="n">AVLTree</span><span class="o">::</span><span class="n">iterator</span><span class="o">::</span><span class="k">operator</span><span class="o">--</span><span class="p">(</span><span class="kt">int</span><span class="p">)</span> <span class="p">{</span>
    <span class="n">iterator</span> <span class="n">t</span> <span class="o">=</span> <span class="o">*</span><span class="k">this</span><span class="p">;</span>
    <span class="n">root</span> <span class="o">=</span> <span class="n">getPre</span><span class="p">(</span><span class="n">head</span><span class="p">,</span> <span class="n">root</span><span class="p">);</span>
    <span class="k">return</span> <span class="n">t</span><span class="p">;</span>
<span class="p">}</span>

<span class="kt">int</span> <span class="n">L_B__</span><span class="o">::</span><span class="n">AVLTree</span><span class="o">::</span><span class="n">iterator</span><span class="o">::</span><span class="k">operator</span><span class="o">*</span><span class="p">()</span> <span class="p">{</span>
    <span class="k">return</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">;</span>
<span class="p">}</span>

<span class="n">L_B__</span><span class="o">::</span><span class="n">AVLTree</span><span class="o">::</span><span class="n">iterator</span> <span class="o">&amp;</span><span class="n">L_B__</span><span class="o">::</span><span class="n">AVLTree</span><span class="o">::</span><span class="n">iterator</span><span class="o">::</span><span class="k">operator</span><span class="o">++</span><span class="p">()</span> <span class="p">{</span>
    <span class="n">root</span> <span class="o">=</span> <span class="n">getNext</span><span class="p">(</span><span class="n">head</span><span class="p">,</span> <span class="n">root</span><span class="p">);</span>
    <span class="k">return</span> <span class="o">*</span><span class="k">this</span><span class="p">;</span>
<span class="p">}</span>

</code></pre></div><h2 id="测试">测试</h2>
<ul>
<li>注意：以下数据<strong>由于存在大量相同的值</strong>，而我写的这个AVLTree并未对相同的值进行存储，所以节省了大量插入时候的调整时间，所以才能达到不错的插入性能，实际上只要<strong>实际插入的数据够多，和红黑树的差距就越大，我之前试过十亿不重复数据插入AVL和RB的测试，AVL运行几分钟，而RB一分钟内解决。但查找和删除方面AVL仍然是吊打RB(毕竟严格平衡树</strong></li>
</ul>
<p>与STL中的set（红黑树）进行对比：
<img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/6bae143e5f9d4b3cac2d989033d541f7.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_17,color_FFFFFF,t_70,g_se,x_16"
        data-srcset="https://img-blog.csdnimg.cn/6bae143e5f9d4b3cac2d989033d541f7.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_17%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16, https://img-blog.csdnimg.cn/6bae143e5f9d4b3cac2d989033d541f7.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_17%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 1.5x, https://img-blog.csdnimg.cn/6bae143e5f9d4b3cac2d989033d541f7.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_17%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/6bae143e5f9d4b3cac2d989033d541f7.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_17,color_FFFFFF,t_70,g_se,x_16"
        title="https://img-blog.csdnimg.cn/6bae143e5f9d4b3cac2d989033d541f7.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_17,color_FFFFFF,t_70,g_se,x_16" /></p>
<h3 id="测试代码">测试代码</h3>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="kt">int</span> <span class="nf">main</span><span class="p">()</span> <span class="p">{</span>
    <span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span>
    <span class="n">AVLTree</span> <span class="n">x</span><span class="p">;</span>
    <span class="n">set</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span><span class="n">Q</span><span class="p">;</span>
    <span class="n">printf</span><span class="p">(</span><span class="s">&#34;插入测试</span><span class="se">\n</span><span class="s">&#34;</span><span class="p">);</span>
    <span class="k">auto</span> <span class="n">start</span> <span class="o">=</span> <span class="n">clock</span><span class="p">();</span>
    <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="mi">100000000</span><span class="p">;</span> <span class="o">++</span><span class="n">i</span><span class="p">)</span> <span class="p">{</span>
            <span class="n">x</span><span class="p">.</span><span class="n">insert</span><span class="p">(</span><span class="n">i</span><span class="o">%</span><span class="mi">10000000</span><span class="p">);</span>
    <span class="p">}</span>
    <span class="n">std</span><span class="o">::</span><span class="n">cout</span><span class="o">&lt;&lt;</span><span class="s">&#34;AVLTree&#34;</span><span class="o">&lt;&lt;</span><span class="n">clock</span><span class="p">()</span><span class="o">-</span><span class="n">start</span><span class="o">&lt;&lt;</span><span class="s">&#34;ms&#34;</span><span class="o">&lt;&lt;</span><span class="n">std</span><span class="o">::</span><span class="n">endl</span><span class="p">;</span>
    <span class="n">start</span> <span class="o">=</span> <span class="n">clock</span><span class="p">();</span>
    <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="mi">100000000</span><span class="p">;</span> <span class="o">++</span><span class="n">i</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">Q</span><span class="p">.</span><span class="n">insert</span><span class="p">(</span><span class="n">i</span><span class="o">%</span><span class="mi">10000000</span><span class="p">);</span>
    <span class="p">}</span>
    <span class="n">std</span><span class="o">::</span><span class="n">cout</span><span class="o">&lt;&lt;</span><span class="s">&#34;RBTree&#34;</span><span class="o">&lt;&lt;</span><span class="n">clock</span><span class="p">()</span><span class="o">-</span><span class="n">start</span><span class="o">&lt;&lt;</span><span class="s">&#34;ms&#34;</span><span class="o">&lt;&lt;</span><span class="n">std</span><span class="o">::</span><span class="n">endl</span><span class="p">;</span>
    <span class="n">printf</span><span class="p">(</span><span class="s">&#34;迭代测试</span><span class="se">\n</span><span class="s">&#34;</span><span class="p">);</span>
    <span class="n">start</span> <span class="o">=</span> <span class="n">clock</span><span class="p">();</span>
    <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="n">it</span> <span class="o">=</span> <span class="n">x</span><span class="p">.</span><span class="n">begin</span><span class="p">();</span><span class="n">it</span><span class="o">!=</span><span class="n">x</span><span class="p">.</span><span class="n">end</span><span class="p">();</span><span class="o">++</span><span class="n">it</span><span class="p">){</span>
        <span class="k">continue</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="n">std</span><span class="o">::</span><span class="n">cout</span><span class="o">&lt;&lt;</span><span class="s">&#34;AVLTree&#34;</span><span class="o">&lt;&lt;</span><span class="n">clock</span><span class="p">()</span><span class="o">-</span><span class="n">start</span><span class="o">&lt;&lt;</span><span class="s">&#34;ms&#34;</span><span class="o">&lt;&lt;</span><span class="n">std</span><span class="o">::</span><span class="n">endl</span><span class="p">;</span>
    <span class="n">start</span> <span class="o">=</span> <span class="n">clock</span><span class="p">();</span>
    <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="n">it</span> <span class="o">=</span> <span class="n">Q</span><span class="p">.</span><span class="n">begin</span><span class="p">();</span><span class="n">it</span><span class="o">!=</span><span class="n">Q</span><span class="p">.</span><span class="n">end</span><span class="p">();</span><span class="o">++</span><span class="n">it</span><span class="p">){</span>
        <span class="k">continue</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="n">std</span><span class="o">::</span><span class="n">cout</span><span class="o">&lt;&lt;</span><span class="s">&#34;RBTree&#34;</span><span class="o">&lt;&lt;</span><span class="n">clock</span><span class="p">()</span><span class="o">-</span><span class="n">start</span><span class="o">&lt;&lt;</span><span class="s">&#34;ms&#34;</span><span class="o">&lt;&lt;</span><span class="n">std</span><span class="o">::</span><span class="n">endl</span><span class="p">;</span>
    <span class="n">printf</span><span class="p">(</span><span class="s">&#34;查找测试</span><span class="se">\n</span><span class="s">&#34;</span><span class="p">);</span>
    <span class="n">start</span> <span class="o">=</span> <span class="n">clock</span><span class="p">();</span>
    <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="mi">100000000</span><span class="p">;</span> <span class="o">++</span><span class="n">i</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">x</span><span class="p">.</span><span class="n">find</span><span class="p">(</span><span class="n">i</span><span class="p">);</span>
    <span class="p">}</span>
    <span class="n">std</span><span class="o">::</span><span class="n">cout</span><span class="o">&lt;&lt;</span><span class="s">&#34;AVLTree&#34;</span><span class="o">&lt;&lt;</span><span class="n">clock</span><span class="p">()</span><span class="o">-</span><span class="n">start</span><span class="o">&lt;&lt;</span><span class="s">&#34;ms&#34;</span><span class="o">&lt;&lt;</span><span class="n">std</span><span class="o">::</span><span class="n">endl</span><span class="p">;</span>
    <span class="n">start</span> <span class="o">=</span> <span class="n">clock</span><span class="p">();</span>
    <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="mi">100000000</span><span class="p">;</span><span class="o">++</span><span class="n">i</span><span class="p">){</span>
        <span class="n">Q</span><span class="p">.</span><span class="n">count</span><span class="p">(</span><span class="n">i</span><span class="p">);</span>
    <span class="p">}</span>
    <span class="n">std</span><span class="o">::</span><span class="n">cout</span><span class="o">&lt;&lt;</span><span class="s">&#34;RBTree&#34;</span><span class="o">&lt;&lt;</span><span class="n">clock</span><span class="p">()</span><span class="o">-</span><span class="n">start</span><span class="o">&lt;&lt;</span><span class="s">&#34;ms&#34;</span><span class="o">&lt;&lt;</span><span class="n">std</span><span class="o">::</span><span class="n">endl</span><span class="p">;</span>
    <span class="n">printf</span><span class="p">(</span><span class="s">&#34;删除测试</span><span class="se">\n</span><span class="s">&#34;</span><span class="p">);</span>
    <span class="n">start</span> <span class="o">=</span> <span class="n">clock</span><span class="p">();</span>
    <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="mi">10000000</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
        <span class="n">x</span><span class="p">.</span><span class="n">remove</span><span class="p">(</span><span class="n">i</span><span class="p">);</span>
    <span class="p">}</span>
    <span class="n">std</span><span class="o">::</span><span class="n">cout</span><span class="o">&lt;&lt;</span><span class="s">&#34;AVLTree&#34;</span><span class="o">&lt;&lt;</span><span class="n">clock</span><span class="p">()</span><span class="o">-</span><span class="n">start</span><span class="o">&lt;&lt;</span><span class="s">&#34;ms&#34;</span><span class="o">&lt;&lt;</span><span class="s">&#34;length&#34;</span><span class="o">&lt;&lt;</span><span class="n">x</span><span class="p">.</span><span class="n">size</span><span class="p">()</span><span class="o">&lt;&lt;</span><span class="n">std</span><span class="o">::</span><span class="n">endl</span><span class="p">;</span>
    <span class="n">start</span> <span class="o">=</span> <span class="n">clock</span><span class="p">();</span>
    <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="mi">10000000</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
        <span class="n">Q</span><span class="p">.</span><span class="n">erase</span><span class="p">(</span><span class="n">i</span><span class="p">);</span>
    <span class="p">}</span>
    <span class="n">std</span><span class="o">::</span><span class="n">cout</span><span class="o">&lt;&lt;</span><span class="s">&#34;RBTree&#34;</span><span class="o">&lt;&lt;</span><span class="n">clock</span><span class="p">()</span><span class="o">-</span><span class="n">start</span><span class="o">&lt;&lt;</span><span class="s">&#34;ms&#34;</span><span class="o">&lt;&lt;</span><span class="s">&#34;length&#34;</span><span class="o">&lt;&lt;</span><span class="n">Q</span><span class="p">.</span><span class="n">size</span><span class="p">()</span><span class="o">&lt;&lt;</span><span class="n">std</span><span class="o">::</span><span class="n">endl</span><span class="p">;</span>
    <span class="k">return</span> <span class="mi">0</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div><h3 id="测试总结">测试总结</h3>
<p>通过不断对比红黑树(RB)和AVL，得出以下结论：</p>
<ol>
<li>插入操作红黑树比AVL快很多，数据量越大优势越明显。</li>
<li>查找和删除操作红黑树却是比AVL慢很多，同样也是数据量越大越明显。</li>
</ol>
<p><strong>总的来说，如果所需要管理的数据量很大，并且需要频繁的插入，那么红黑树更适合你，如果只需要插入一次后，对数据进行查找管理，那么AVL更加的适合你！</strong></p>
<h2 id="解题测试">解题测试</h2>
<p><img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/325acab00af947199c7d4cf6f2b33b74.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        data-srcset="https://img-blog.csdnimg.cn/325acab00af947199c7d4cf6f2b33b74.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16, https://img-blog.csdnimg.cn/325acab00af947199c7d4cf6f2b33b74.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 1.5x, https://img-blog.csdnimg.cn/325acab00af947199c7d4cf6f2b33b74.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/325acab00af947199c7d4cf6f2b33b74.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        title="https://img-blog.csdnimg.cn/325acab00af947199c7d4cf6f2b33b74.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16" />
<a href="https://www.nowcoder.com/pat/5/problem/4117" target="_blank" rel="noopener noreffer">OJ平台</a></p>
<blockquote>
<p>在以上设计的基础上加个get_head方法即可。</p>
</blockquote>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="cp">#include</span> <span class="cpf">&lt;bits/stdc++.h&gt;</span><span class="cp">
</span><span class="cp"></span>
<span class="k">struct</span> <span class="nc">node</span> <span class="p">{</span>
    <span class="kt">int</span> <span class="n">val</span><span class="p">;</span>
    <span class="kt">int</span> <span class="n">depth</span><span class="p">;</span>
    <span class="n">node</span> <span class="o">*</span><span class="n">lchild</span><span class="p">;</span>
    <span class="n">node</span> <span class="o">*</span><span class="n">rchild</span><span class="p">;</span>

    <span class="n">node</span><span class="p">()</span> <span class="o">:</span> <span class="n">val</span><span class="p">(</span><span class="mi">0</span><span class="p">),</span> <span class="n">lchild</span><span class="p">(</span><span class="k">nullptr</span><span class="p">),</span> <span class="n">rchild</span><span class="p">(</span><span class="k">nullptr</span><span class="p">)</span> <span class="p">{}</span>

    <span class="n">node</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">)</span> <span class="o">:</span> <span class="n">val</span><span class="p">(</span><span class="n">x</span><span class="p">),</span> <span class="n">lchild</span><span class="p">(</span><span class="k">nullptr</span><span class="p">),</span> <span class="n">rchild</span><span class="p">(</span><span class="k">nullptr</span><span class="p">)</span> <span class="p">{}</span>
<span class="p">};</span>

<span class="k">class</span> <span class="nc">AVLTree</span> <span class="p">{</span>
    <span class="cm">/*date part*/</span>
    <span class="n">node</span> <span class="o">*</span><span class="n">head</span><span class="p">;</span>
    <span class="kt">int</span> <span class="n">size</span><span class="p">;</span>
<span class="k">public</span><span class="o">:</span>
    <span class="cm">/*construct and destruct part*/</span>
    <span class="n">AVLTree</span><span class="p">()</span> <span class="o">:</span> <span class="n">head</span><span class="p">(</span><span class="k">nullptr</span><span class="p">),</span><span class="n">size</span><span class="p">(</span><span class="mi">0</span><span class="p">)</span> <span class="p">{}</span>

    <span class="n">AVLTree</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">)</span> <span class="o">:</span> <span class="n">head</span><span class="p">(</span><span class="k">new</span> <span class="n">node</span><span class="p">(</span><span class="n">x</span><span class="p">)),</span><span class="n">size</span><span class="p">(</span><span class="mi">1</span><span class="p">)</span> <span class="p">{}</span>

    <span class="o">~</span><span class="n">AVLTree</span><span class="p">()</span> <span class="p">{</span>
        <span class="n">destroy</span><span class="p">(</span><span class="n">head</span><span class="p">);</span>
    <span class="p">}</span>

<span class="k">private</span><span class="o">:</span>
    <span class="cm">/*static function part*/</span>
    <span class="k">static</span> <span class="n">node</span> <span class="o">*</span><span class="n">rotateRight</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">)</span> <span class="p">{</span><span class="c1">//右旋
</span><span class="c1"></span>        <span class="n">node</span> <span class="o">*</span><span class="n">son</span> <span class="o">=</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">;</span>
        <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span> <span class="o">=</span> <span class="n">son</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">;</span>
        <span class="n">son</span><span class="o">-&gt;</span><span class="n">rchild</span> <span class="o">=</span> <span class="n">root</span><span class="p">;</span>
        <span class="n">update_depth</span><span class="p">(</span><span class="n">root</span><span class="p">);</span><span class="c1">//更新深度(右旋只会对这两结点产生影响
</span><span class="c1"></span>        <span class="n">update_depth</span><span class="p">(</span><span class="n">son</span><span class="p">);</span>
        <span class="k">return</span> <span class="n">son</span><span class="p">;</span>
    <span class="p">}</span>

    <span class="k">static</span> <span class="n">node</span> <span class="o">*</span><span class="nf">rotateLeft</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">node</span> <span class="o">*</span><span class="n">son</span> <span class="o">=</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">;</span>
        <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span> <span class="o">=</span> <span class="n">son</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">;</span>
        <span class="n">son</span><span class="o">-&gt;</span><span class="n">lchild</span> <span class="o">=</span> <span class="n">root</span><span class="p">;</span>
        <span class="n">update_depth</span><span class="p">(</span><span class="n">root</span><span class="p">);</span>
        <span class="n">update_depth</span><span class="p">(</span><span class="n">son</span><span class="p">);</span>
        <span class="k">return</span> <span class="n">son</span><span class="p">;</span>
    <span class="p">}</span>

    <span class="k">static</span> <span class="n">node</span> <span class="o">*</span><span class="nf">rotateLeftRight</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span> <span class="o">=</span> <span class="n">rotateLeft</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">);</span>
        <span class="k">return</span> <span class="n">rotateRight</span><span class="p">(</span><span class="n">root</span><span class="p">);</span>
    <span class="p">}</span>

    <span class="k">static</span> <span class="n">node</span> <span class="o">*</span><span class="nf">rotateRightLeft</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span> <span class="o">=</span> <span class="n">rotateRight</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">);</span>
        <span class="k">return</span> <span class="n">rotateLeft</span><span class="p">(</span><span class="n">root</span><span class="p">);</span>
    <span class="p">}</span>

    <span class="k">static</span> <span class="kt">void</span> <span class="nf">destroy</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">root</span> <span class="o">==</span> <span class="k">nullptr</span><span class="p">)</span>
            <span class="k">return</span><span class="p">;</span>
        <span class="n">destroy</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">);</span>
        <span class="n">destroy</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">);</span>
        <span class="k">delete</span> <span class="n">root</span><span class="p">;</span>
        <span class="n">root</span> <span class="o">=</span> <span class="k">nullptr</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="k">static</span> <span class="n">node</span><span class="o">*</span> <span class="nf">getMinNode</span><span class="p">(</span><span class="n">node</span><span class="o">*</span> <span class="n">root</span><span class="p">){</span>
        <span class="k">if</span><span class="p">(</span><span class="n">root</span><span class="o">==</span> <span class="k">nullptr</span><span class="p">)</span>
            <span class="k">return</span> <span class="k">nullptr</span><span class="p">;</span>
        <span class="k">while</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="o">!=</span> <span class="k">nullptr</span><span class="p">)</span>
            <span class="n">root</span> <span class="o">=</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">;</span>
        <span class="k">return</span> <span class="n">root</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="k">static</span> <span class="n">node</span><span class="o">*</span> <span class="nf">getMaxNode</span><span class="p">(</span><span class="n">node</span><span class="o">*</span> <span class="n">root</span><span class="p">){</span>
        <span class="k">if</span><span class="p">(</span><span class="n">root</span><span class="o">==</span> <span class="k">nullptr</span><span class="p">)</span>
            <span class="k">return</span> <span class="k">nullptr</span><span class="p">;</span>
        <span class="k">while</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="o">!=</span> <span class="k">nullptr</span><span class="p">)</span>
            <span class="n">root</span> <span class="o">=</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">;</span>
        <span class="k">return</span> <span class="n">root</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="k">static</span> <span class="kt">int</span> <span class="nf">get_depth</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">)</span> <span class="p">{</span><span class="c1">//得到深度
</span><span class="c1"></span>        <span class="k">if</span> <span class="p">(</span><span class="n">root</span> <span class="o">==</span> <span class="k">nullptr</span><span class="p">)</span>
            <span class="k">return</span> <span class="mi">0</span><span class="p">;</span>
        <span class="k">return</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">depth</span><span class="p">;</span>
    <span class="p">}</span>

    <span class="k">static</span> <span class="kt">void</span> <span class="nf">update_depth</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">root</span> <span class="o">==</span> <span class="k">nullptr</span><span class="p">)</span>
            <span class="k">return</span><span class="p">;</span>
        <span class="n">root</span><span class="o">-&gt;</span><span class="n">depth</span> <span class="o">=</span> <span class="n">std</span><span class="o">::</span><span class="n">max</span><span class="p">(</span><span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">),</span> <span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">))</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span>
    <span class="p">}</span>

    <span class="k">static</span> <span class="n">node</span> <span class="o">*</span><span class="nf">Insert</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">,</span> <span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">)</span> <span class="p">{</span><span class="c1">//所有的deep的更新都在后序遍历后
</span><span class="c1"></span>        <span class="k">if</span> <span class="p">(</span><span class="n">root</span> <span class="o">==</span> <span class="k">nullptr</span><span class="p">)</span> <span class="p">{</span>
            <span class="n">root</span> <span class="o">=</span> <span class="k">new</span> <span class="n">node</span><span class="p">(</span><span class="n">x</span><span class="p">);</span>
        <span class="p">}</span> <span class="k">else</span> <span class="k">if</span> <span class="p">(</span><span class="n">x</span> <span class="o">&lt;=</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">)</span> <span class="p">{</span>
            <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span> <span class="o">=</span> <span class="n">Insert</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">);</span>
            <span class="c1">//由于在更新该root结点之前，当平衡度未达到该要求之前肯定以及是进行了update_depth操作
</span><span class="c1"></span>            <span class="k">if</span> <span class="p">(</span><span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">)</span> <span class="o">-</span> <span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">)</span> <span class="o">==</span> <span class="mi">2</span><span class="p">)</span>
                <span class="n">root</span> <span class="o">=</span> <span class="n">x</span> <span class="o">&lt;=</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="o">-&gt;</span><span class="n">val</span> <span class="o">?</span> <span class="n">rotateRight</span><span class="p">(</span><span class="n">root</span><span class="p">)</span> <span class="o">:</span> <span class="n">rotateLeftRight</span><span class="p">(</span><span class="n">root</span><span class="p">);</span>
        <span class="p">}</span> <span class="k">else</span> <span class="k">if</span> <span class="p">(</span><span class="n">x</span> <span class="o">&gt;</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">)</span> <span class="p">{</span>
            <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span> <span class="o">=</span> <span class="n">Insert</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">);</span>
            <span class="k">if</span> <span class="p">(</span><span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">)</span> <span class="o">-</span> <span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">)</span> <span class="o">==</span> <span class="o">-</span><span class="mi">2</span><span class="p">)</span>
                <span class="n">root</span> <span class="o">=</span> <span class="n">x</span> <span class="o">&gt;=</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="o">-&gt;</span><span class="n">val</span> <span class="o">?</span> <span class="n">rotateLeft</span><span class="p">(</span><span class="n">root</span><span class="p">)</span> <span class="o">:</span> <span class="n">rotateRightLeft</span><span class="p">(</span><span class="n">root</span><span class="p">);</span>
        <span class="p">}</span>
        <span class="n">update_depth</span><span class="p">(</span><span class="n">root</span><span class="p">);</span>
        <span class="k">return</span> <span class="n">root</span><span class="p">;</span>
    <span class="p">}</span>

    <span class="k">static</span> <span class="n">node</span> <span class="o">*</span><span class="nf">remove</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">,</span> <span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">root</span> <span class="o">==</span> <span class="k">nullptr</span><span class="p">)</span>
            <span class="k">return</span> <span class="k">nullptr</span><span class="p">;</span>

        <span class="k">if</span> <span class="p">(</span><span class="n">x</span> <span class="o">==</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">)</span> <span class="p">{</span>
            <span class="cm">/*左右子树均不为空---用中序的前驱或者后继来进行替换*/</span>
            <span class="k">if</span> <span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span> <span class="o">!=</span> <span class="k">nullptr</span> <span class="o">&amp;&amp;</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span> <span class="o">!=</span> <span class="k">nullptr</span><span class="p">)</span> <span class="p">{</span>
                <span class="cm">/*根据左右子树的深度来选择删除替换哪边的*/</span>
                <span class="k">if</span><span class="p">(</span><span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">)</span><span class="o">&gt;</span><span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">)){</span>
                    <span class="n">node</span><span class="o">*</span> <span class="n">t</span> <span class="o">=</span> <span class="n">getMaxNode</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">);</span>
                    <span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span> <span class="o">=</span> <span class="n">t</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">;</span>
                    <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span> <span class="o">=</span> <span class="n">remove</span><span class="p">(</span><span class="n">t</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">,</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">);</span>
                <span class="p">}</span><span class="k">else</span><span class="p">{</span>
                    <span class="n">node</span><span class="o">*</span> <span class="n">t</span> <span class="o">=</span> <span class="n">getMinNode</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">);</span>
                    <span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span> <span class="o">=</span> <span class="n">t</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">;</span>
                    <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span> <span class="o">=</span> <span class="n">remove</span><span class="p">(</span><span class="n">t</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">,</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">);</span>
                <span class="p">}</span>
            <span class="p">}</span>
            <span class="cm">/*左右子树至少有一个为空的情况，直接往下走一步即可*/</span>
            <span class="k">else</span><span class="p">{</span>
                <span class="n">node</span><span class="o">*</span> <span class="n">tmp</span> <span class="o">=</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="o">==</span> <span class="k">nullptr</span><span class="o">?</span><span class="n">root</span><span class="o">-&gt;</span><span class="nl">rchild</span><span class="p">:</span> <span class="k">nullptr</span><span class="p">;</span>
                <span class="k">if</span><span class="p">(</span><span class="n">tmp</span><span class="o">!=</span> <span class="k">nullptr</span><span class="p">){</span>
                    <span class="o">*</span><span class="n">root</span> <span class="o">=</span> <span class="o">*</span><span class="n">tmp</span><span class="p">;</span>
                    <span class="k">delete</span> <span class="n">tmp</span><span class="p">;</span>
                <span class="p">}</span>
                <span class="k">else</span><span class="p">{</span>
                    <span class="k">delete</span> <span class="n">root</span><span class="p">;</span>
                    <span class="n">root</span> <span class="o">=</span> <span class="k">nullptr</span><span class="p">;</span>
                <span class="p">}</span>
            <span class="p">}</span>
        <span class="p">}</span> <span class="k">else</span> <span class="k">if</span> <span class="p">(</span><span class="n">x</span> <span class="o">&lt;</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">)</span> <span class="p">{</span>
            <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span> <span class="o">=</span> <span class="n">remove</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">);</span>
            <span class="k">if</span><span class="p">(</span><span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">)</span><span class="o">-</span><span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">)</span><span class="o">==-</span><span class="mi">2</span><span class="p">)</span>
                <span class="n">root</span> <span class="o">=</span> <span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">)</span><span class="o">&gt;</span><span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">)</span><span class="o">?</span><span class="n">rotateRightLeft</span><span class="p">(</span><span class="n">root</span><span class="p">)</span><span class="o">:</span> <span class="n">rotateLeft</span><span class="p">(</span><span class="n">root</span><span class="p">);</span>
        <span class="p">}</span> <span class="k">else</span> <span class="p">{</span>
            <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span> <span class="o">=</span> <span class="n">remove</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">);</span>
            <span class="k">if</span><span class="p">(</span><span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">)</span><span class="o">-</span><span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">)</span><span class="o">==</span><span class="mi">2</span><span class="p">)</span>
                <span class="n">root</span> <span class="o">=</span> <span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">)</span><span class="o">&gt;</span><span class="n">get_depth</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">)</span><span class="o">?</span><span class="n">rotateLeftRight</span><span class="p">(</span><span class="n">root</span><span class="p">)</span><span class="o">:</span> <span class="n">rotateRight</span><span class="p">(</span><span class="n">root</span><span class="p">);</span>
        <span class="p">}</span>
        <span class="k">return</span> <span class="n">root</span><span class="p">;</span>
    <span class="p">}</span>

    <span class="k">static</span> <span class="kt">void</span> <span class="nf">inorder</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">root</span> <span class="o">!=</span> <span class="k">nullptr</span><span class="p">)</span> <span class="p">{</span>
            <span class="n">inorder</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">);</span>
            <span class="n">printf</span><span class="p">(</span><span class="s">&#34;%d &#34;</span><span class="p">,</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">);</span>
            <span class="n">inorder</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">);</span>
        <span class="p">}</span>
    <span class="p">}</span>

<span class="k">public</span><span class="o">:</span>
    <span class="cm">/*public function part*/</span>
    <span class="kt">void</span> <span class="n">insert</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">)</span> <span class="p">{</span>
        <span class="c1">//递归方式插入，方便后续处理
</span><span class="c1"></span>        <span class="n">head</span> <span class="o">=</span> <span class="n">Insert</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">head</span><span class="p">);</span>
        <span class="n">size</span><span class="o">++</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="kt">void</span> <span class="nf">remove</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">){</span>
        <span class="n">assert</span><span class="p">(</span><span class="n">size</span><span class="o">!=</span><span class="mi">0</span><span class="p">);</span>
        <span class="n">head</span> <span class="o">=</span> <span class="n">remove</span><span class="p">(</span><span class="n">x</span><span class="p">,</span><span class="n">head</span><span class="p">);</span>
        <span class="n">size</span><span class="o">--</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="kt">void</span> <span class="nf">clear</span><span class="p">()</span> <span class="p">{</span>
        <span class="n">destroy</span><span class="p">(</span><span class="n">head</span><span class="p">);</span>
    <span class="p">}</span>

    <span class="kt">bool</span> <span class="nf">isEmpty</span><span class="p">()</span> <span class="p">{</span>
        <span class="k">return</span> <span class="n">head</span> <span class="o">==</span> <span class="k">nullptr</span><span class="p">;</span>
    <span class="p">}</span>

    <span class="kt">bool</span> <span class="nf">find</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">)</span> <span class="p">{</span>
        <span class="c1">//查找直接迭代方式即可
</span><span class="c1"></span>        <span class="n">node</span> <span class="o">*</span><span class="n">f</span> <span class="o">=</span> <span class="n">head</span><span class="p">;</span>
        <span class="k">while</span> <span class="p">(</span><span class="n">f</span> <span class="o">!=</span> <span class="k">nullptr</span><span class="p">)</span> <span class="p">{</span>
            <span class="k">if</span> <span class="p">(</span><span class="n">x</span> <span class="o">==</span> <span class="n">f</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">)</span>
                <span class="k">return</span> <span class="nb">true</span><span class="p">;</span>
            <span class="k">else</span> <span class="k">if</span> <span class="p">(</span><span class="n">x</span> <span class="o">&lt;</span> <span class="n">f</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">)</span>
                <span class="n">f</span> <span class="o">=</span> <span class="n">f</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">;</span>
            <span class="k">else</span>
                <span class="n">f</span> <span class="o">=</span> <span class="n">f</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="k">return</span> <span class="nb">false</span><span class="p">;</span>
    <span class="p">}</span>

    <span class="kt">void</span> <span class="nf">inorder_print</span><span class="p">()</span> <span class="p">{</span>
        <span class="n">printf</span><span class="p">(</span><span class="s">&#34;Inorder:# &#34;</span><span class="p">);</span>
        <span class="n">inorder</span><span class="p">(</span><span class="n">head</span><span class="p">);</span>
    <span class="p">}</span>
    <span class="n">node</span><span class="o">*</span> <span class="nf">get_head</span><span class="p">(){</span>
        <span class="k">return</span> <span class="n">head</span><span class="p">;</span>
    <span class="p">}</span>
<span class="p">};</span>

<span class="kt">int</span> <span class="nf">main</span><span class="p">()</span> <span class="p">{</span>
    <span class="n">AVLTree</span> <span class="n">x</span><span class="p">;</span>
    <span class="kt">int</span> <span class="n">n</span><span class="p">;</span><span class="n">std</span><span class="o">::</span><span class="n">cin</span><span class="o">&gt;&gt;</span><span class="n">n</span><span class="p">;</span>
    <span class="k">while</span><span class="p">(</span><span class="n">n</span><span class="o">--</span><span class="p">){</span>
        <span class="kt">int</span> <span class="n">t</span><span class="p">;</span>
        <span class="n">std</span><span class="o">::</span><span class="n">cin</span><span class="o">&gt;&gt;</span><span class="n">t</span><span class="p">;</span>
        <span class="n">x</span><span class="p">.</span><span class="n">insert</span><span class="p">(</span><span class="n">t</span><span class="p">);</span>
    <span class="p">}</span>
    <span class="n">printf</span><span class="p">(</span><span class="s">&#34;%d&#34;</span><span class="p">,</span><span class="n">x</span><span class="p">.</span><span class="n">get_head</span><span class="p">()</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">);</span>
    <span class="k">return</span> <span class="mi">0</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div></div><div class="post-footer" id="post-footer">
    <div class="post-info"><div class="post-info-tag"><span><a href="/tags/%E5%BE%92%E6%89%8B%E5%86%99%E7%9A%84avl%E7%AB%9F%E7%84%B6%E6%AF%94stl%E4%B8%AD%E7%9A%84%E7%BA%A2%E9%BB%91%E6%A0%91%E6%95%88%E7%8E%87%E6%9B%B4%E9%AB%98/">徒手写的AVL竟然比STL中的红黑树效率更高？✨</a>
                </span></div><div class="post-info-line"><div class="post-info-mod">
                <span>更新于 2022-02-16</span>
            </div><div class="post-info-mod"></div>
        </div><div class="post-info-share">
            <span><a href="javascript:void(0);" title="分享到 Twitter" data-sharer="twitter" data-url="https://acking-you.github.io/posts/%E5%BE%92%E6%89%8B%E5%86%99%E7%9A%84avl%E7%AB%9F%E7%84%B6%E6%AF%94stl%E4%B8%AD%E7%9A%84%E7%BA%A2%E9%BB%91%E6%A0%91%E6%95%88%E7%8E%87%E6%9B%B4%E9%AB%98/" data-title="徒手写的AVL竟然比STL中的红黑树效率更高？✨" data-hashtags="徒手写的AVL竟然比STL中的红黑树效率更高？✨"><i class="fab fa-twitter fa-fw"></i></a><a href="javascript:void(0);" title="分享到 Facebook" data-sharer="facebook" data-url="https://acking-you.github.io/posts/%E5%BE%92%E6%89%8B%E5%86%99%E7%9A%84avl%E7%AB%9F%E7%84%B6%E6%AF%94stl%E4%B8%AD%E7%9A%84%E7%BA%A2%E9%BB%91%E6%A0%91%E6%95%88%E7%8E%87%E6%9B%B4%E9%AB%98/" data-hashtag="徒手写的AVL竟然比STL中的红黑树效率更高？✨"><i class="fab fa-facebook-square fa-fw"></i></a><a href="javascript:void(0);" title="分享到 WhatsApp" data-sharer="whatsapp" data-url="https://acking-you.github.io/posts/%E5%BE%92%E6%89%8B%E5%86%99%E7%9A%84avl%E7%AB%9F%E7%84%B6%E6%AF%94stl%E4%B8%AD%E7%9A%84%E7%BA%A2%E9%BB%91%E6%A0%91%E6%95%88%E7%8E%87%E6%9B%B4%E9%AB%98/" data-title="徒手写的AVL竟然比STL中的红黑树效率更高？✨" data-web><i class="fab fa-whatsapp fa-fw"></i></a><a href="javascript:void(0);" title="分享到 Line" data-sharer="line" data-url="https://acking-you.github.io/posts/%E5%BE%92%E6%89%8B%E5%86%99%E7%9A%84avl%E7%AB%9F%E7%84%B6%E6%AF%94stl%E4%B8%AD%E7%9A%84%E7%BA%A2%E9%BB%91%E6%A0%91%E6%95%88%E7%8E%87%E6%9B%B4%E9%AB%98/" data-title="徒手写的AVL竟然比STL中的红黑树效率更高？✨"><i class="fab fa-line fa-fw"></i></a><a href="javascript:void(0);" title="分享到 微博" data-sharer="weibo" data-url="https://acking-you.github.io/posts/%E5%BE%92%E6%89%8B%E5%86%99%E7%9A%84avl%E7%AB%9F%E7%84%B6%E6%AF%94stl%E4%B8%AD%E7%9A%84%E7%BA%A2%E9%BB%91%E6%A0%91%E6%95%88%E7%8E%87%E6%9B%B4%E9%AB%98/" data-title="徒手写的AVL竟然比STL中的红黑树效率更高？✨" data-image="https://img-blog.csdnimg.cn/img_convert/8db816efd6abe83538c4d47108d9c840.png#pic_center"><i class="fab fa-weibo fa-fw"></i></a><a href="javascript:void(0);" title="分享到 Myspace" data-sharer="myspace" data-url="https://acking-you.github.io/posts/%E5%BE%92%E6%89%8B%E5%86%99%E7%9A%84avl%E7%AB%9F%E7%84%B6%E6%AF%94stl%E4%B8%AD%E7%9A%84%E7%BA%A2%E9%BB%91%E6%A0%91%E6%95%88%E7%8E%87%E6%9B%B4%E9%AB%98/" data-title="徒手写的AVL竟然比STL中的红黑树效率更高？✨" data-description="徒手写的AVL竟然比STL中的红黑树效率更高？✨"><i data-svg-src="/lib/simple-icons/icons/myspace.min.svg"></i></a><a href="javascript:void(0);" title="分享到 Blogger" data-sharer="blogger" data-url="https://acking-you.github.io/posts/%E5%BE%92%E6%89%8B%E5%86%99%E7%9A%84avl%E7%AB%9F%E7%84%B6%E6%AF%94stl%E4%B8%AD%E7%9A%84%E7%BA%A2%E9%BB%91%E6%A0%91%E6%95%88%E7%8E%87%E6%9B%B4%E9%AB%98/" data-title="徒手写的AVL竟然比STL中的红黑树效率更高？✨" data-description="徒手写的AVL竟然比STL中的红黑树效率更高？✨"><i class="fab fa-blogger fa-fw"></i></a><a href="javascript:void(0);" title="分享到 Evernote" data-sharer="evernote" data-url="https://acking-you.github.io/posts/%E5%BE%92%E6%89%8B%E5%86%99%E7%9A%84avl%E7%AB%9F%E7%84%B6%E6%AF%94stl%E4%B8%AD%E7%9A%84%E7%BA%A2%E9%BB%91%E6%A0%91%E6%95%88%E7%8E%87%E6%9B%B4%E9%AB%98/" data-title="徒手写的AVL竟然比STL中的红黑树效率更高？✨"><i class="fab fa-evernote fa-fw"></i></a></span>
        </div></div><div class="post-nav"><a href="/posts/%E6%96%B0%E6%89%8B%E7%94%A8c&#43;&#43;%E5%86%99%E4%BA%86%E4%B8%AA%E6%B3%9B%E5%9E%8B%E5%A0%86%E6%95%88%E7%8E%87%E7%AB%9F%E6%AF%94stl%E7%9A%84%E6%9B%B4%E5%BF%AB/" class="prev" rel="prev" title="新手用C&#43;&#43;写了个泛型堆，效率竟比STL的更快？"><i class="fas fa-angle-left fa-fw"></i>Previous Post</a>
            <a href="/posts/java%E8%BF%9E%E6%8E%A5%E6%95%B0%E6%8D%AE%E5%BA%93/" class="next" rel="next" title="Java连接数据库">Next Post<i class="fas fa-angle-right fa-fw"></i></a></div></div>
</div></article></div>
            </main>
            <footer class="footer"><div class="footer-container"><div class="footer-line">由 <a href="https://gohugo.io/" target="_blank" rel="noopener noreffer" title="Hugo 0.86.0">Hugo</a> 强力驱动 | 主题 - <a href="https://github.com/khusika/FeelIt" target="_blank" rel="noopener noreffer" title="FeelIt 1.0.1"><i class="fas fa-hand-holding-heart fa-fw"></i> FeelIt</a>
        </div><div class="footer-line" itemscope itemtype="http://schema.org/CreativeWork"><i class="far fa-copyright fa-fw"></i><span itemprop="copyrightYear">2023</span><span class="author" itemprop="copyrightHolder">&nbsp;<a href="/"></a></span></div>
</div>
</footer>
        </div>

        <div id="fixed-buttons"><a href="#" id="back-to-top" class="fixed-button" title="回到顶部">
                <i class="fas fa-chevron-up fa-fw"></i>
            </a></div><link rel="stylesheet" href="/lib/fontawesome-free/all.min.css"><link rel="stylesheet" href="/lib/animate/animate.min.css"><link rel="stylesheet" href="/lib/katex/katex.min.css"><link rel="stylesheet" href="/lib/katex/copy-tex.min.css"><script src="/lib/autocomplete/autocomplete.min.js"></script><script src="/lib/lunr/lunr.min.js"></script><script src="/lib/lunr/lunr.stemmer.support.min.js"></script><script src="/lib/lunr/lunr.zh.min.js"></script><script src="/lib/lazysizes/lazysizes.min.js"></script><script src="/lib/clipboard/clipboard.min.js"></script><script src="/lib/sharer/sharer.min.js"></script><script src="/lib/katex/katex.min.js"></script><script src="/lib/katex/auto-render.min.js"></script><script src="/lib/katex/copy-tex.min.js"></script><script src="/lib/katex/mhchem.min.js"></script><script>window.config={"code":{"copyTitle":"复制到剪贴板","maxShownLines":200},"comment":{},"math":{"delimiters":[{"display":true,"left":"$$","right":"$$"},{"display":true,"left":"\\[","right":"\\]"},{"display":false,"left":"$","right":"$"},{"display":false,"left":"\\(","right":"\\)"}],"strict":false},"search":{"highlightTag":"em","lunrIndexURL":"/index.json","lunrLanguageCode":"zh","lunrSegmentitURL":"/lib/lunr/lunr.segmentit.js","maxResultLength":100,"noResultsFound":"没有找到结果","snippetLength":50,"type":"lunr"}};</script><script src="/js/theme.min.js"></script></body></html>
